思想

双指针算法不仅应用于链表，在数组等数据结构中也有广泛应用。
核心思路是指向问题中的关键节点，根据问题的上下文逻辑变换位置，最终解决问题。

实例

合并K个升序链表 leetcode 23

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

输入：
lists: List[ListNode]，一组升序链表

输出：
ListNode，将所有链表合并到一个升序链表中，返回合并后的链表。

举例：
当 lists = [[1,4,5],[1,3,4],[2,6]] 时，返回的合并升序链表是 [1,1,2,3,4,4,5,6]。

关键点

这里的关键点选出一组升序链表中的最小元素，在两个升序链表合并的时候可以用双指针解决，当扩展为 K
个升序链表的时候就需要一个数据结构来快速筛选，合适的是最小堆，将一组待比较的链表节点放入最小堆，每次获取堆顶的最小值，再将这个节点的后续元素放入堆中。

编码

from queue import PriorityQueue

from typing import List, Optional


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


def merge_k_sorted_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    # 定义小顶堆
    class ListNodePriorityQueue:
        def __init__(self, node: ListNode):
            self.node = node

        def __lt__(self, other):
            return self.node.val < other.node.val

    dummy = ListNode()
    cur = dummy
    # 初始化，将 K 个升序链表关键点放入小顶堆
    head_heap = PriorityQueue()
    for list_head in lists:
        if list_head is not None:
            head_heap.put(ListNodePriorityQueue(list_head))
    # 遍历 K 个升序链表全部节点,通过小顶堆获得当前最小值，并补充后续节点
    while not head_heap.empty():
        # 获取当前最小节点
        node = head_heap.get().node
        cur.next = node
        if node.next is not None:
            head_heap.put(ListNodePriorityQueue(node.next))
        cur = cur.next
    return dummy.next