Day 3 链表 拓展：21.合并，23. 合并k个，86. 分割, 876. 中点

小结

• 合并两个有序链表

• 链表的分解

• 合并 k 个有序链表

• 寻找单链表的倒数第 k 个节点

• 寻找单链表的中点

• 判断单链表是否包含环并找出环起点

• 判断两个单链表是否相交并找出交点

21. Merge Two Sorted Lists

• 思路
  • example
  • 双指针 （1个指针track1个链表），dummyhead
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummyhead = ListNode(0)
        cur = dummyhead  
        while list1 and list2:  
            if list1.val < list2.val:
                cur.next = list1  
                list1 = list1.next  
            else:
                cur.next = list2  
                list2 = list2.next  
            cur = cur.next  
        if list1:
            cur.next = list1  
        if list2:
            cur.next = list2  
        return dummyhead.next  

23. Merge k Sorted Lists

• 思路
  • example
  • 优先队列， 最小堆 (size k)
    • 这样可以快速得到当前k个里面的最小值

最小堆元素：(value, index)

• 复杂度. 时间：, 空间:

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        pq = []
        dummyhead = ListNode(-1)
        cur = dummyhead  
        n = len(lists)
        for i in range(n):
            if lists[i]:
                heapq.heappush(pq, (lists[i].val, i))
        while pq: 
            val, i = heapq.heappop(pq)  
            cur.next = lists[i] 
            if lists[i].next != None:
                lists[i] = lists[i].next # 修改了list[i] （标记当前head)
                heapq.heappush(pq, (lists[i].val, i)) 
            cur = cur.next  
        return dummyhead.next

86. Partition List

• 思路
  • example
  • 分成两个链表 （< x，>= x），然后合并。
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        dummyhead1 = ListNode(-1)
        dummyhead2 = ListNode(-1)
        cur1, cur2 = dummyhead1, dummyhead2  
        while head: 
            if head.val < x:
                cur1.next = head  
                cur1 = cur1.next  
            else:
                cur2.next = head  
                cur2 = cur2.next  
            head = head.next  
        cur2.next = None  # 否则可能出现闭环
        cur1.next = dummyhead2.next  
        return dummyhead1.next 

876. Middle of the Linked List

• 思路
  • example
  • 双指针: 快慢
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head  
        while fast and fast.next:
            slow = slow.next 
            fast = fast.next.next  
        return slow