[数据结构与算法]python--leetcode 双指针技巧秒杀七道链表题目

23. 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

使用小跟堆（https://labuladong.gitee.io/algo/2/22/64/）
以及python 标准库 heapq （https://www.jianshu.com/p/801318c77ab5）

nums = [2, 3, 5, 1, 54, 23, 132]
heap = []
for num in nums:
    heapq.heappush(heap, num)  # 加入堆

print(heap[0])  # 如果只是想获取最小值而不是弹出，使用heap[0]
print([heapq.heappop(heap) for _ in range(len(nums))])  # 注意这里是len(nums) 而不是heap，因为根据总共个数进行heappop排序
# out: [1, 2, 3, 5, 23, 54, 132]

另：链表题目

        res = ListNode(-1)
        head = res #记录头节点
        for xxx
            temp = ListNode()
            res.next = temp
            res = res.next
        return head.next

进阶：只使用k个节点保存小根堆
python 重载运算符定义Listnode节点的大小比较
小根堆保存k个节点，在节点弹出后，heappush进这个节点在list中的下一个节点

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

        def __lt__(l1, l2):
            return a.val < b.val
        ListNode.__lt__ = __lt__

这时，heapq就可以调用重载的比较符号进行比较

        minHeap = []
        for x in lists:
            if x:
                heapq.heappush(minHeap, (x))

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        def __lt__(l1,l2):
            return l1.val < l2.val
        ListNode.__lt__ = __lt__
        minheap=[]
        for l in lists:
            if l:
                heapq.heappush(minheap, l)
        res = ListNode(-1)
        pre = res
        while(len(minheap)!=0):
            store = heapq.heappop(minheap)
            pre.next = store
            pre = pre.next
            if(store.next):
                heapq.heappush(minheap, store.next)
        return res.next

2 。删除倒数第k个节点，这种不能预知长度的，可以用两个节点一起移动的方法
链表环入口问题：
慢: L+R
快: L+R+circle
2k - k = circle -> k = circle

快指针离环入口: circle - R
慢走过了k步 L + R = k
求 L = k - R = circle - R
所以快指针保留不动，继续完成剩下的圈就走了circle - R步 即L
所以慢指针移动到head，两个指针再次相遇的点即入口

判断两个链表相交的节点
a遍历lista再遍历listb
b遍历listb再遍历lista
找到第一个相等节点

一般使用快慢指针，快指针需要调用.next.next，所以循环条件需要是

while(quick and quick.next)

避免Nonetype have no next 的问题