24. 两两交换链表中的节点

样例
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 # 下个循环，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.环形链表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