問題描述：【Linked List】61. Rotate List

解題思路：

這道題是給一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)結(jié)點(diǎn)向右移動(dòng) k 個(gè)位置。

1、先計(jì)算鏈表長度 size，k = k % size，如果 k % size == 0，則不用移動(dòng)，直接返回 head；
2、否則，需要將前 size - k 個(gè)結(jié)點(diǎn)移動(dòng)到后面。因此只需要循環(huán) size - k 次，找到新鏈表頭部，然后進(jìn)行指針的交換。最后返回新鏈表頭即可。

注意：這道題雖然是旋轉(zhuǎn)鏈表，但是實(shí)際上并沒有真正的進(jìn)行結(jié)點(diǎn)的移動(dòng)，只是進(jìn)行了指針的交換。

時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。

Python3 實(shí)現(xiàn)：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return head
        cur, size = head, 1
        while cur.next:  # cur 結(jié)束后記錄鏈表尾
            size += 1
            cur = cur.next
        k = k % size
        if k == 0:  # 不用旋轉(zhuǎn)
            return head
        i, pre, newhead = 0, None, head  # pre:newhead的前一個(gè), newhead:新頭部
        while i < size - k:
            i += 1
            pre = newhead
            newhead = newhead.next
        cur.next = head
        pre.next = None
        return newhead

問題描述：【Linked List】82. Remove Duplicates from Sorted List II

解題思路：

這道題是給一個(gè)鏈表，去除鏈表中重復(fù)的元素，只留下原鏈表出現(xiàn)過一次的數(shù)字。如 1->2->2->3 變成 1->3。

這道題和下面的 Leetcode 82 思路相同，只不過這道題不需要留下重復(fù)的元素。因此除了 Leetcode 82 中的 cur 和 last 外，還需要一個(gè) pre 指向 cur 的前一個(gè)位置，便于把所有相同的 cur 全部刪除。 同時(shí)，要使用一個(gè)標(biāo)記變量 flag 來記錄連續(xù)一段有沒有重復(fù)的元素（flag = True），如果沒有重復(fù)，只是修改 pre 和 cur 向后各移動(dòng)一位；否則還要進(jìn)行指針的交換。注意：比如 [1,2,2,2,2] 這種，循環(huán)結(jié)束了，但是最后 flag 為 True，因此還需要再進(jìn)行一次判斷，如果 flag 為 True，要進(jìn)行一次指針的交換操作。

時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。

Python3 實(shí)現(xiàn)：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        node = ListNode(-1)
        node.next = head
        head = node
        if not head.next:
            return head.next
        # cur: 指向第一個(gè)重復(fù)的元素，last: 工作指針，pre: 是 cur 的前一個(gè)位置
        pre, cur, last = head, head.next, head.next.next
        flag = False
        while last:
            if cur.val == last.val:
                flag = True
                cur.next = last.next
            elif flag:  # 有重復(fù)
                pre.next = last
                cur = last
                flag = False    # 不要忘了修改 flag 為 False，標(biāo)記下一段是否可能有重復(fù)
            elif not flag:  # 沒有重復(fù)
                pre = cur
                cur = last
            last = last.next
        if flag:  # [1,1]或者[1,2,2]
             pre.next = last 
        return head.next

問題描述：【Linked List】83. Remove Duplicates from Sorted List

解題思路：

這道題是給一個(gè)鏈表，去除鏈表中重復(fù)的元素。如 1->2->2->3 變成 1->2->3。

只需要兩個(gè)指針 cur 和 last，cur 指向相同元素的第一個(gè)結(jié)點(diǎn)，last 為工作指針，每次向后移動(dòng)。剩下的就是指針的交換和移動(dòng)。時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。

Python3 實(shí)現(xiàn)：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        cur, last = head, head.next
        while last:
            if cur.val == last.val:
                cur.next = last.next
            else:
                cur = cur.next
            last = last.next
        return head

問題描述：【Two Pointers】142. Linked List Cycle II

解題思路：

這道題是給一個(gè)鏈表，判斷是否有環(huán)。如果有環(huán)，找到環(huán)的起始位置。

這道題和 Leetcode 【Two Pointers】141. Linked List Cycle 思路一致，都是先使用快慢指針（一個(gè)走一步，一個(gè)走兩步）判斷是否有環(huán)。

對于這道題，如果有環(huán)，還要尋找環(huán)的起始位置。思路是：定義一個(gè)指針 begin 指向鏈表頭，然后和快慢指針的相遇點(diǎn) slow（或者 fast），每一次都各走一步，直到二者相遇。證明就不寫了，可以參考：LeetCode-142. Linked List Cycle II（詳細(xì)證明）與龜兔賽跑算法 的證明過程。

時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。

Python3 實(shí)現(xiàn)：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        flag = True  # 標(biāo)記是否有環(huán)
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:  # 有環(huán)
                flag = False
                break
        if flag:  # 無環(huán)
            return None
        begin = head
        while begin != slow:
            begin = begin.next
            slow = slow.next
        return begin # return slow

問題描述：【Linked List】143. Reorder List

解題思路：

這道題是給一個(gè)鏈表，按照 L0→Ln→L1→Ln-1→L2→Ln-2→… 重新排序。

首先第一種想法：遍歷一次鏈表，將各個(gè)結(jié)點(diǎn)保存到 list 中，按題目順序重新構(gòu)造鏈表即可。更進(jìn)一步，我們只需要保存后一半鏈表元素到 list 中，然后將 list 中的元素插入到前半段鏈表中。但是，這樣的操作時(shí)間復(fù)雜度和空間復(fù)雜度均為 O(n)。

有沒有時(shí)間復(fù)雜度為 O(n)、空間復(fù)雜度為 O(1) 的做法？因?yàn)楹蟀攵涡枰催^來插入，因此我們可以對后半段鏈表進(jìn)行反轉(zhuǎn)，然后再按順序插入到前半段鏈表就行。鏈表反轉(zhuǎn)可以參考 Leetcode 【Linked List】206. Reverse Linked List。

實(shí)際上，當(dāng)我們遇到需要從尾部操作的鏈表問題（如這道題和 Leetcode 【Linked List】445. Add Two Numbers II），都可以先將鏈表反轉(zhuǎn)，然后再操作，這樣就不用使用額外空間了。

Python3 實(shí)現(xiàn)：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return head
        l1 = slow = head
        fast = head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        l2 = self.reverse(slow.next)  # 后半段反轉(zhuǎn)
        slow.next = None  # 斷開前半段
        cur1, cur2 = l1, l2  
        while cur1 and cur2:  # 將后半段依次插入前半段
            l2 = l2.next  # 插入
            cur2.next = cur1.next
            cur1.next = cur2
            cur1 = cur2.next  # 移動(dòng)
            cur2 = l2
        return l1
        
    def reverse(self, head):
        if not head or not head.next:
            return head
        pre, cur = head, head.next
        while cur:
            pre.next = cur.next  # 交換
            cur.next = head
            head = cur
            if pre != None:
                cur = pre.next  # 移動(dòng)
        return head

問題描述：【Hash Table】1171. Remove Zero Sum Consecutive Nodes from Linked List

解題思路：

這道題是給一個(gè)鏈表，反復(fù)刪去鏈表中總和為 0 的連續(xù)結(jié)點(diǎn)組成的序列，直到不存在這樣的序列為止。

很明顯這是一道前綴和問題。之前做過前綴和的一個(gè)專題：Leetcode【523、525、560、974】，因此需要用到 Hash Table 存儲(chǔ)未出現(xiàn)的前綴和與對應(yīng)位置的鏈表結(jié)點(diǎn)地址。如果再出現(xiàn)相同前綴和，則就刪除兩前綴和地址之間的元素即可（修改指針指向）。

注意：
1、要把 {0: None} 加入到 Hash Table 中，作為前綴和的出口（如 [1,2,-3] 這種情況）。
2、對于鏈表 [1,3,2,-3,-2,5,5,-5,1]，從左到右遍歷，剛開始得到的前綴和分別為 {0: add(None), 1: add(1), 4: add(3), 6: add(2), 3: add(-3)}，當(dāng)計(jì)算到 -2 位置時(shí)，前綴和為 3 + (-1) = 1，前綴和 1 之前在 Hash Table 中出現(xiàn)過，因此需要將 add(1) 的下一個(gè)地址指向 -2 的下一個(gè)地址 add(5)。但是要注意，這時(shí)候還要標(biāo)記 add(1) 后面的前綴和不可用（因?yàn)橐呀?jīng)被刪除了）。因此，這個(gè)時(shí)候可以再使用一個(gè)集合 discard，用來記錄刪除的那些地址（從 add(1) 的下一個(gè)位置開始循環(huán)，一直到 add(-2)）。因此，不僅前綴和要在之前出現(xiàn)過，而且前綴和地址不是 discard 中刪除的地址，才可以進(jìn)行刪除。如果不這樣做，當(dāng)碰到 add(5) 時(shí)，前綴和為 6，又要?jiǎng)h除，從而造成錯(cuò)誤的結(jié)果。

時(shí)間復(fù)雜度為 O(n^2)，空間復(fù)雜度為 O(n)。

Python3 實(shí)現(xiàn)：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        node = ListNode(-1)
        node.next = head
        head = node
        dic = {0: head}  # 前綴和:地址
        discard = set()  # 刪除的地址
        presum = 0
        cur = head.next
        while cur:
            presum += cur.val
            if presum in dic and dic[presum] not in discard:
                p = dic[presum].next  # 刪除的地址保存在集合中
                while p != cur:
                    discard.add(p)
                    p = p.next
                dic[presum].next = cur.next  # 指針移動(dòng)
            else:
                dic[presum] = cur
            cur = cur.next
        return head.next