24. 兩兩交換鏈表中的節(jié)點

樣例
dummmy->15-> 12-> 73-> 24
......cur.........0.......1......2......4..

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:

        dummy_head = ListNode(next = head) # 構造虛擬頭結點
        cur = dummy_head

        while cur.next and cur.next.next: # 考慮鏈表長度為奇數和偶數2中情況，2中情況判斷邏輯不能調換
            temp1 = cur.next # 提前保留 0 和 2的value，否則dummy指向位置1時，會丟失位置0的值
            temp2 = cur.next.next.next # 1 指向位置 0 時，會丟失位置 2 的值

            cur.next = cur.next.next #dummmy的next -> 12
            cur.next.next = temp1 # 12 -> 15
            temp1.next = temp2 # 15 -> 73
            cur = cur.next.next # 下個循環(huán)，cur從12開始
        return dummy_head.next

19. 刪除鏈表的倒數第 N 個結點

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:

        dummy_head = ListNode(next = head) # 虛擬頭結點
        slow, fast = dummy_head, dummy_head # 定義快慢指針

        while n >= 0 and fast: # 快指針先移動 n+1 步
            fast = fast.next
            n -= 1
        while fast: # 快慢指針同時移動
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy_head.next

160.鏈表相交

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        
        cur_a = headA
        cur_b = headB

        while cur_a != cur_b:
            cur_a = cur_a.next if cur_a else headA  # 如果a走完了，切換到b走
            cur_b = cur_b.next if cur_a else headB
        return cur_a

142.環(huán)形鏈表II

推導公式
slow: x + y
fast: x +y + n(y + z) ,n為圈數
當 n = 1時，(x + y) * 2 = x + y + n (y + z) -> x = z

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:

        slow, fast  = head, head # 2個指針同時從head開始移動

        while fast and fast.next: 
            fast = fast.next.next # 快指針移動2
            slow = slow.next # 慢指針移動1
            if fast == slow:
                index1 = head
                index2 = fast
                while  index1 != index2:
                    index1 = index1.next
                    index2 = index2.next
                return index1
        return None