代码随想训练营第四天（Python）｜ 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、02.07. 链表相交、142.环形链表II

两两交换链表中的节点
关键点：涉及到头节点变动的都使用虚拟节点。画图找出交换节点指向的顺序和退出循环的条件。
1、迭代法

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_node = ListNode(next=head)
        cur = dummy_node       # 这里需要操作 2 个节点的位置，所以cur 指向2个节点前的位置好操作
        while cur.next != None and cur.next.next != None: # 画图写出跳出循环的条件
            first = cur.next            # 临时变量记录下第一个节点
            next_first = cur.next.next.next # 临时变量记录下第二轮的第一个节点
            cur.next = cur.next.next        # cur 指向交换位置的节点 second
            cur.next.next = first      # 交换了 second 和 first 的位置
            first.next = next_first     # 连接上后面的节点
            cur = first                 # 移动指针 cur 的位置 或者 cur = cur.next.next
        return dummy_node.next

2、递归法

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        first = head                # 第一轮的第一个节点
        second = head.next          # 第一轮的第二个节点
        next_first = head.next.next  # 第二轮的第一个节点

        second.next = first         # 交换第一和第二个节点
        first.next = self.swapPairs(next_first)  # 连接后续交换顺序的接点
        return second

19.删除链表的倒数第N个节点

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head is None:
            return head
        dummy_node = ListNode(next=head)
        slow = fast = dummy_node
        while n+1 and fast != None:   # 这里 n+1 是让快节点比慢节点多走一步，因为是需要删除 n 处的节点
            fast = fast.next
            n -= 1
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy_node.next

02.07. 链表相交
等比例法，双指针分别走完 headA 和 headB 后，要么相聚在相交节点，要么是空节点

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA is None or headB is None:
            return
        p1 = headA
        p2 = headB
        while p1 != p2:
            p1 = p1.next if p1 else headB # 走完 headA 后走 headB, 都走完了为 None 或者是相交节点
            p2 = p2.next if p2 else headA
        return p1

142.环形链表II
快慢指针 fast = 2slow。
x（启始节点到环入口的距离）
y（环入口到相遇点的距离）
z（相遇点到环入口的距离）
slow = x + y
fast = x + (y+z)n (n>=1)
2(x+y) = x + y + (y+z)n
x = (n-1)*(y+z) + z

    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:  # 快慢指针相遇
                new_slow = slow
                new_fast = head
                while new_slow != new_fast:
                    new_fast = new_fast.next
                    new_slow = new_slow.next
                return new_slow
        return