今日任务

1. LeetCode24 两两交换链表中的节点
2. LeetCode19 删除链表的倒数第N个节点
3. LeetCode160 链表相交
4. LeetCode142 环形链表Ⅱ

今日心情：今天意外在图书馆抢到了带插座的座位。在做题中确实学习了不少，收获颇丰。

资料来源：

1. 代码随想录 | LeetCode24 两两交换链表中的节点
2. 代码随想录 | LeetCode19 删除链表的倒数第N个节点
3. 代码随想录 | LeetCode160 链表相交
4. 代码随想录 | LeetCode142 环形链表Ⅱ

1 LeetCode24 两两交换链表中的节点

输入：head = [1,2,3,4]
输出：[2,1,4,3]

输入：head = []
输出：[]

输入：head = [1]
输出：[1]

看了思路之后才能写得出来，确实是硬模拟，但是必须想明白一次交换的过程中，谁先操作，谁后操作（看注释）。

python
from typing import Optional

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        virtual_head = ListNode(next=head)
        point = virtual_head
        if head is None:
            return None
        while True:
            if point.next is None:
                break
            if point.next.next is None:
                break
            temp1 = point.next
            temp2 = point.next.next.next  
            # 0 -> 1 -> 2 -> 3 —> 4 point -> 0 temp1 -> 1 temp2 -> 3
            point.next = point.next.next  # 0 -> 2 1 -> 2 -> 3 —> 4
            point.next.next = temp1  # 0 -> 2 -> 1 -> 2 -> 1  3 —> 4
            temp1.next = temp2  # 0 -> 2 -> 1 -> 3 —> 4
            point = temp1
        return virtual_head.next

2 LeetCode19 删除链表的倒数第N个节点

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

一看双指针，忽然就懂了怎么做了。两个指针都指向虚拟头节点，然后先移动一个指针n次，然后两个指针一起进入循环，直到先移动的指针到达链表尾节点，此时后移动的指针指向的即为要删除的节点的前一个节点。

python
from typing import Optional

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head.next is None:
            if n == 1:
                return None
            else:
                return head
        virtual_head = ListNode(next=head)
        before, after = virtual_head, virtual_head
        for _ in range(n):
            after = after.next
        while after is not None and after.next is not None:
            after = after.next
            before = before.next
        before.next = before.next.next
        return virtual_head.next

3 LeetCode160 链表相交

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

这个思路应该想到的，没想到是失策了，还是看着文档写出来的。先求得两个链表的长度，然后移动长链表的指针，移动到剩余长度和短链表相同时，两个指针一起循环移动和比较，只要两个指针指向的是同一个节点，就证明两个链表有相交。

python
from typing import Optional

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        length_a, length_b = 1, 1
        point_a, point_b = headA, headB
        while point_a.next is not None:
            point_a = point_a.next
            length_a += 1
        while point_b.next is not None:
            point_b = point_b.next
            length_b += 1
        # 之后length_a特指较长的那个链表
        if length_a <= length_b:
            gap = length_b - length_a
            point_a = headB
            point_b = headA
        else:
            gap = length_a - length_b
            point_a = headA
            point_b = headB
        while gap > 0:
            point_a = point_a.next
            gap -= 1
        while point_a is not None:
            if point_a == point_b:
                return point_a
            else:
                point_a = point_a.next
                point_b = point_b.next
        return None

4 LeetCode142 环形链表Ⅱ

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

这题确实学习了关于判断是否有环和如何确定进环位置的知识。

4.1 链表是否有环？

设定双指针，在循环中快指针每次向前移动2个节点，慢指针每次向前移动1个节点。如果快慢指针在某一时刻指向同一个节点，那么链表中有环。如果快指针指向的节点或者快指针的下一个节点为空，那么链表无环。

推导：如果链表有环，那么快慢指针必定在某个时刻先后进环。一旦进环，快慢指针的移动方式等效于快指针在以一次一个节点的速度靠近慢指针。所以在环里，它俩必定相遇。

4.2 如何确定进环位置？

在使用上述方法确定有环之后，使两个指针一个指向头节点，一个在原地不改变指向，两个节点同时按一次一个节点的速度移动，那么两个指针相遇的节点即为进环位置。

推导：按照之前的移动方式，在慢指针正式进环的时候，快指针所在的节点向后看离进环位置的距离一定等于进环位置离头节点的距离（即慢指针所移动过的距离）①。

反过来想，快指针所在的节点向前看离慢指针（即进环位置）的距离，也是之后两个指针相遇时所在的节点向后看距离进环位置的距离②。因为按照两个指针的移动方式，从慢指针进环开始，两个指针之间的距离会以每次一个节点的速度减少。那么由此可知，两个指针之间的距离为0时，慢指针移动过的距离就等于慢指针进环时，快指针向前看和慢指针的距离。

因为环的周长固定，如果快慢指针相遇时所在的节点向后看距离进环位置的距离是慢节点进环时快指针所在的节点向前看离进环位置的距离，那么快慢指针相遇时所在的节点向前看距离进环位置的距离，即为慢指针进环时，快指针所在的节点向后看离进环位置的距离，也是进环位置离头节点的距离③。所以从快慢指针相遇时所在的节点和头节点同时出发，以每次一个节点的速度移动，必定会在进环位置相遇。

如图，根据以上的推导，先得到$x = y$（①），再得到$z = z'$（②），最后得到$y' = y = x$（③）。（图中箭头方向即为所谓“向前”，“向后”的依据，箭头方向为前）

python
from typing import Optional

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast_point, slow_point = head, head
        while fast_point is not None and fast_point.next is not None:
            fast_point = fast_point.next.next
            slow_point = slow_point.next

            if fast_point == slow_point:
                fast_point = head
                while True:
                    if fast_point == slow_point:
                        return fast_point
                    fast_point = fast_point.next
                    slow_point = slow_point.next
        return None