leetcode链表双指针练习题

21. 合并两个有序链表

用两个指针分别指向链表 A、B 的头节点，每次比较当前节点的值，把较小的节点接到结果链表尾部，再移动对应指针。这里用虚拟头节点简化连接操作，复用原来的节点即可。某条链表为空时结束循环，把另一条链表的剩余部分直接接到结果尾部。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:
        # 使用虚拟头节点，简化问题。
        dummy = ListNode(-1)
        head = dummy
        # 不停比较两个元素当前指向位置的元素大小，然后添加到新列表
        while list1 is not None and list2 is not None:
            if list1.val < list2.val:
                head.next = list1
                list1 = list1.next
            else:
                head.next = list2
                list2 = list2.next
            head = head.next
        # 如果有链表依然不为空，直接添加到新链表即可。
        if list1 is not None:
            head.next = list1
        if list2 is not None:
            head.next = list2
        return dummy.next

86. 分隔链表

题目要求小于 x 的节点出现在大于等于 x 的节点之前，并保持各自的相对顺序。可以用两个虚拟头节点分别组织 D1、D2：从前往后遍历原链表，小于 x 的节点接到 D1 尾部，其余节点接到 D2 尾部。这样各部分的顺序保持不变，最后将 D2 接到 D1 后面即可。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        # 创建两个虚拟头节点。
        dummy1 = ListNode(-1)
        dummy2 = ListNode(-1)
        head1, head2 = dummy1, dummy2
        # 遍历链表
        while head is not None:
            # 如果值小于x就接到D1后面，否则就接到D2后面
            if head.val < x:
                head1.next = head
                head1 = head1.next
                head = head.next
                head1.next = None
            else:
                head2.next = head
                head2 = head2.next
                head = head.next
                head2.next = None
        # 把D2链表接到D1链表后面即可
        head1.next = dummy2.next
        return dummy1.next

23. 合并 K 个升序链表

与合并两个链表类似，每次都要取出当前最小的头节点，只是候选变成了 K 个。可以把候选放入最小堆，每次弹出最小节点，接到结果尾部，再把它的后继节点放回堆中。堆里保存“节点值、链表次序、节点”三元组：元组先比较节点值，值相同再比较链表次序，避免直接比较不支持大小关系的 ListNode 对象。每条链表在堆中最多保留一个候选，所以链表次序足以区分这些节点。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        dummy = ListNode(-1)
        h = dummy
        pq = []
        for i, node in enumerate(lists):
            if node is not None:
                heapq.heappush(pq, (node.val, i, node))
        while pq:
            val, i, node = heapq.heappop(pq)
            h.next = node
            h = h.next
            if node.next is not None:
                heapq.heappush(pq, (node.next.val, i, node.next))
        return dummy.next

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

找倒数第 N 个节点，可以先遍历求长度，再走到对应位置；也可以只遍历一次。让 p1 先从头节点走 n 步，再让 p2 从头节点出发，两个指针同步前进。p1 到达空节点时，p2 就在倒数第 n 个节点，因为两者始终相差 n 步。

删除节点时，需要找到它的前驱，也就是倒数第 N+1 个节点，再修改 next。这里加入虚拟头节点，并让两个指针从它出发，可以统一处理删除头节点、删除后链表为空等边界情况。

# Definition for singly-linked list.
# 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]:
        dummy = ListNode(-1)
        dummy.next = head
        p1 = dummy
        p2 = dummy
        for i in range(n + 1):
            p1 = p1.next
        while p1 is not None:
            p1 = p1.next
            p2 = p2.next
        p2.next = p2.next.next
        return dummy.next

876. 链表的中间结点

直观做法是先求链表总长度，再遍历到中间位置。使用快慢指针可以一次完成：slow 和 fast 初始都指向头节点，slow 每次走一步，fast 每次走两步。fast 到达末尾时，slow 刚好走过约一半的距离，停在中间节点。

链表长度为偶数、有两个中间节点时，这种写法返回后面的那个。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
        return slow

141. 环形链表

继续使用快慢指针。如果链表有环，快指针会在环内追上慢指针；如果快指针先到达空节点，就说明没有环。

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


class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = head
        fast = head
        while fast != None and slow != None:
            if fast.next != None:
                fast = fast.next.next
            else:
                return False
            slow = slow.next
            if fast == slow:
                return True
        return False

142. 环形链表 II

先用第 141 题的方法找到相遇点。假设相遇时 slow 走了 k 步，fast 走了 2k 步，那么多走的 k 步一定是环长的整数倍。若 slow 入环后到相遇点走了 m 步，头节点到环入口的距离就是 k-m。从相遇点再走 k-m 步也会回到入口，因为加上已经走过的 m 步，刚好是环长的整数倍。因此，相遇后把 slow 放回头节点，让两者每次都走一步，再次相遇的位置就是环入口。

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


class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        if fast == None or fast.next == None:
            return None
        slow = head
        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow

160. 相交链表

两条链表长度可能不同，直接同步向后走不能保证同时进入公共部分。可以让 p1 走完 A 后接着走 B，p2 走完 B 后接着走 A。两条路线的总长度相同，因此能够对齐。这里切换的是遍历指针，并不需要实际修改链表连接。

例如，链表 A 为 a1->a2->c1->c2。

链表 B 为 b1->b2->b3->c1->c2。

按图中的路线交换起点后，两个指针会在共同节点 c1 相遇。如果没有公共节点，两者最终都会走到 None，循环同样结束并返回 None，表示链表不相交。

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        p1,p2=headA,headB
        while p1!=p2:
            if p1 is None:
                p1=headB
            else:
                p1=p1.next
            if p2 is None:
                p2=headA
            else:
                p2=p2.next
        return p1