一、將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回

方法一：迭代
首先，我們?cè)O(shè)定一個(gè)哨兵節(jié)點(diǎn) "prehead" ，這可以在最后讓我們比較容易地返回合并后的鏈表。我們維護(hù)一個(gè) prev 指針，我們需要做的是調(diào)整它的 next 指針。然后，我們重復(fù)以下過(guò)程，直到 l1 或者 l2 指向了 null ：如果 l1 當(dāng)前位置的值小于等于 l2 ，我們就把 l1 的值接在 prev 節(jié)點(diǎn)的后面同時(shí)將 l1 指針往后移一個(gè)。否則，我們對(duì) l2 做同樣的操作。不管我們將哪一個(gè)元素接在了后面，我們都把 prev 向后移一個(gè)元素。
在循環(huán)終止的時(shí)候， l1 和 l2 至多有一個(gè)是非空的。由于輸入的兩個(gè)鏈表都是有序的，所以不管哪個(gè)鏈表是非空的，它包含的所有元素都比前面已經(jīng)合并鏈表中的所有元素都要大。這意味著我們只需要簡(jiǎn)單地將非空鏈表接在合并鏈表的后面，并返回合并鏈表。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode preHead = new ListNode(-1);
        ListNode prev = preHead;
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return preHead.next;
    }
}

鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode/

方法二：遞歸

• 終止條件：兩條鏈表分別名為 l1 和 l2，當(dāng) l1 為空或 l2 為空時(shí)結(jié)束
• 返回值：每一層調(diào)用都返回排序好的鏈表頭
• 本級(jí)遞歸內(nèi)容：如果 l1 的 val 值更小，則將 l1.next 與排序好的鏈表頭相接，l2 同理

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

鏈接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/hua-jie-suan-fa-21-he-bing-liang-ge-you-xu-lian-bi/

二、給定一個(gè)排序鏈表，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次。

// 由于輸入的列表已排序，因此我們可以通過(guò)將結(jié)點(diǎn)的值與它之后的結(jié)點(diǎn)進(jìn)行比較來(lái)確定它是否為重復(fù)結(jié)點(diǎn)。如果它是重復(fù)的，我們更改當(dāng)前結(jié)點(diǎn)的 next 指針，以便它跳過(guò)下一個(gè)結(jié)點(diǎn)并直接指向下一個(gè)結(jié)點(diǎn)之后的結(jié)點(diǎn)
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while(current != null && current.next != null) {
            if(current.val == current.next.val) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return head;
    }
}

三、給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。

方法一：哈希表
我們遍歷所有結(jié)點(diǎn)并在哈希表中存儲(chǔ)每個(gè)結(jié)點(diǎn)。如果當(dāng)前結(jié)點(diǎn)為空結(jié)點(diǎn) null（即已檢測(cè)到鏈表尾部的下一個(gè)結(jié)點(diǎn)），那么我們已經(jīng)遍歷完整個(gè)鏈表，并且該鏈表不是環(huán)形鏈表。如果當(dāng)前結(jié)點(diǎn)的引用已經(jīng)存在于哈希表中，那么返回 true（即該鏈表為環(huán)形鏈表）
方法二：快慢指針
首先創(chuàng)建兩個(gè)不同速度的節(jié)點(diǎn)，如果兩個(gè)節(jié)點(diǎn)相同時(shí)，則代表該鏈表是環(huán)形鏈表；
若不相同時(shí)，判斷快指針當(dāng)前節(jié)點(diǎn)/下一個(gè)節(jié)點(diǎn)是否到達(dá)終點(diǎn)(即null)，若為null則不是環(huán)形鏈表，否則移動(dòng)節(jié)點(diǎn)

class Solution {
    public boolean hasCycle(ListNode head) {
        /// 1、哈希表
        // Set<ListNode> map = new HashSet<>();
        // while(head != null) {
        //     if(map.contains(head)) {
        //         return true;
        //     } else {
        //         map.add(head);
        //     }
        //     head = head.next;
        // } 
        // return false;

        /// 2、快慢指針
        ListNode slow = head, fast = head.next;
        while (slow != fast) {
            if(fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

四、找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。

方法一、暴力遍歷
對(duì)鏈表A中的每一個(gè)結(jié)點(diǎn) a ，遍歷整個(gè)鏈表 B 并檢查鏈表 B 中是否存在結(jié)點(diǎn)和 a 相同。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /// 暴力遍歷
        while(headA != null) {
            ListNode temp = headB;
            while(temp != null) {
                if(headA == temp) {
                    return headA;
                } else {
                    temp = temp.next;
                }
            }
            headA = headA.next;
        }
        return headA;
    }
}

方法二、哈希表
遍歷鏈表 A 并將每個(gè)結(jié)點(diǎn)存儲(chǔ)在哈希表中。然后檢查鏈表 B 中的每一個(gè)結(jié)點(diǎn) b 是否在哈希表中。若在，則 b為相交結(jié)點(diǎn)

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /// 哈希表
        Set<ListNode> set = new HashSet<>();
        while(headA != null || headA.next != null) {
            if(headB == null || headB.next == null) return null;
            if(set.contains(headB)) {
                return headB;
            } else {
                set.add(headA);
            }
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}

方法三、雙指針

• 創(chuàng)建兩個(gè)指針 pA 和 pB，分別初始化為鏈表 A 和 B 的頭結(jié)點(diǎn)。然后讓它們向后逐結(jié)點(diǎn)遍歷。
• 當(dāng) pA 到達(dá)鏈表的尾部時(shí)，將它重定位到鏈表 B 的頭結(jié)點(diǎn); 類(lèi)似的，當(dāng) pB 到達(dá)鏈表的尾部時(shí)，將它重定位到鏈表 A 的頭結(jié)點(diǎn)。
• 若在某一時(shí)刻 pA 和 pB 相遇，則 pA/pB 為相交結(jié)點(diǎn)。
• 想弄清楚為什么這樣可行, 可以考慮以下兩個(gè)鏈表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于結(jié)點(diǎn) 9。 由于 B.length (=4) < A.length (=6)，pB 比 pA 少經(jīng)過(guò) 2 個(gè)結(jié)點(diǎn)，會(huì)先到達(dá)尾部。將 pB 重定向到 A 的頭結(jié)點(diǎn)，pApA 重定向到 B 的頭結(jié)點(diǎn)后，pB 要比 pA 多走 2 個(gè)結(jié)點(diǎn)。因此，它們會(huì)同時(shí)到達(dá)交點(diǎn)。
• 如果兩個(gè)鏈表存在相交，它們末尾的結(jié)點(diǎn)必然相同。因此當(dāng) pA/pB 到達(dá)鏈表結(jié)尾時(shí)，記錄下鏈表 A/B 對(duì)應(yīng)的元素。若最后元素不相同，則兩個(gè)鏈表不相交。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /// 雙指針
        ListNode pA = headA, pB = headB;
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

五、刪除鏈表中等于給定值 val 的所有節(jié)點(diǎn)。

示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
這里需要注意的是：如果刪除的節(jié)點(diǎn)位于鏈表的頭部時(shí) ，我們使用哨兵節(jié)點(diǎn)來(lái)解決該問(wèn)題

• 初始化哨兵節(jié)點(diǎn)為 ListNode(0) 且設(shè)置 sentinel.next = head。
• 初始化兩個(gè)指針 curr 和 prev 指向當(dāng)前節(jié)點(diǎn)和前繼節(jié)點(diǎn)。
• 當(dāng) curr != null：
• 比較當(dāng)前節(jié)點(diǎn)和要?jiǎng)h除的節(jié)點(diǎn)：
• 若當(dāng)前節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)：則 prev.next = curr.next。
• 否則設(shè) prve = curr。
• 遍歷下一個(gè)元素：curr = curr.next。
• 返回 sentinel.next。
  注：哨兵節(jié)點(diǎn)廣泛應(yīng)用于樹(shù)和鏈表中，如偽頭、偽尾、標(biāo)記等，它們是純功能的，通常不保存任何數(shù)據(jù)，其主要目的是使鏈表標(biāo)準(zhǔn)化，如使鏈表永不為空、永不無(wú)頭、簡(jiǎn)化插入和刪除。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode sentinel = new ListNode(0); // 哨兵節(jié)點(diǎn)，虛擬增加一個(gè)頭結(jié)點(diǎn)
        sentinel.next = head;
        
        ListNode prev = sentinel, curr = head;
        while (curr != null) {
            if (curr.val == val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            } 
            curr = curr.next;
        }
        return sentinel.next;
    }
}

六、翻轉(zhuǎn)鏈表

class Solution {
    public ListNode reverseList(ListNode head) {
        // 1、 迭代
        // ListNode preHead = null;
        // ListNode prev = head;
        // while(prev != null) {
        //     ListNode temp = prev.next;
        //     prev.next = preHead;
        //     preHead = prev;
        //     prev = temp;
        // }
        // return preHead;

        /// 2、 遞歸
        if (head == null || head.next == null) return head;
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

七、請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。

先翻轉(zhuǎn)鏈表 再比較

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head, prev = null, prepre = null;
        while(fast != null && fast.next != null) {
            /// 移動(dòng)指針
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
            /// 翻轉(zhuǎn)前半部鏈表
            prev.next = prepre;
            prepre = prev;

        }
        if(fast != null) { slow = slow.next;} // 鏈表為奇數(shù)，需要去除中間節(jié)點(diǎn)
        // 遍歷 對(duì)比
        while (prev != null && slow != null) {
            if (slow.val != prev.val) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }
        return true;
    }
}

八、請(qǐng)編寫(xiě)一個(gè)函數(shù)，使其可以刪除某個(gè)鏈表中給定的（非末尾）節(jié)點(diǎn)

從鏈表里刪除一個(gè)節(jié)點(diǎn) node 的最常見(jiàn)方法是修改之前節(jié)點(diǎn)的 next 指針，使其指向之后的節(jié)點(diǎn)。
在這里我們無(wú)法訪(fǎng)問(wèn)我們想要?jiǎng)h除的節(jié)點(diǎn) 之前 的節(jié)點(diǎn)，我們始終不能修改該節(jié)點(diǎn)的 next 指針。但是我們可以將想要?jiǎng)h除的節(jié)點(diǎn)的值替換為它后面節(jié)點(diǎn)中的值，然后刪除它之后的節(jié)點(diǎn)。
因?yàn)槲覀冎酪獎(jiǎng)h除的節(jié)點(diǎn)不是列表的末尾，所以我們可以保證這種方法是可行的。

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

九、給定一個(gè)帶有頭結(jié)點(diǎn) head 的非空單鏈表，返回鏈表的中間結(jié)點(diǎn)。如果有兩個(gè)中間結(jié)點(diǎn)，則返回第二個(gè)中間結(jié)點(diǎn)。

使用雙指針，通過(guò)快慢指針找到中間點(diǎn)

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // fast != null && fast.next != null 用于找到第二個(gè)中間節(jié)點(diǎn)
        // fast.next != null && fast.next.next != null 用于找到第一個(gè)中間節(jié)點(diǎn)
        while( fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

十、給你一個(gè)單鏈表的引用結(jié)點(diǎn) head。鏈表中每個(gè)結(jié)點(diǎn)的值不是 0 就是 1。已知此鏈表是一個(gè)整數(shù)數(shù)字的二進(jìn)制表示形式。

請(qǐng)你返回該鏈表所表示數(shù)字的 十進(jìn)制值 。

class Solution {
    public int getDecimalValue(ListNode head) {
        int sum = 0;
        while (head != null) {
            sum = sum * 2 + head.val;
            head = head.next;
        }
        return sum;
    }
}

注: 以上鏈表問(wèn)題皆來(lái)源于https://leetcode-cn.com/problems/