思想
雙指針?biāo)惴ú粌H應(yīng)用于鏈表，在數(shù)組等數(shù)據(jù)結(jié)構(gòu)中也有廣泛應(yīng)用。
核心思路是指向問題中的關(guān)鍵節(jié)點(diǎn)，根據(jù)問題的上下文邏輯變換位置，最終解決問題。
實(shí)例
合并K個(gè)升序鏈表 leetcode 23
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
輸入：
lists: List[ListNode]，一組升序鏈表
輸出：
ListNode，將所有鏈表合并到一個(gè)升序鏈表中，返回合并后的鏈表。
舉例：
當(dāng) lists = [[1,4,5],[1,3,4],[2,6]] 時(shí)，返回的合并升序鏈表是 [1,1,2,3,4,4,5,6]。
關(guān)鍵點(diǎn)
這里的關(guān)鍵點(diǎn)選出一組升序鏈表中的最小元素，在兩個(gè)升序鏈表合并的時(shí)候可以用雙指針解決，當(dāng)擴(kuò)展為 K
個(gè)升序鏈表的時(shí)候就需要一個(gè)數(shù)據(jù)結(jié)構(gòu)來快速篩選，合適的是最小堆，將一組待比較的鏈表節(jié)點(diǎn)放入最小堆，每次獲取堆頂?shù)淖钚≈?，再將這個(gè)節(jié)點(diǎn)的后續(xù)元素放入堆中。
編碼
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 個(gè)升序鏈表關(guān)鍵點(diǎn)放入小頂堆
head_heap = PriorityQueue()
for list_head in lists:
if list_head is not None:
head_heap.put(ListNodePriorityQueue(list_head))
# 遍歷 K 個(gè)升序鏈表全部節(jié)點(diǎn),通過小頂堆獲得當(dāng)前最小值，并補(bǔ)充后續(xù)節(jié)點(diǎn)
while not head_heap.empty():
# 獲取當(dāng)前最小節(jié)點(diǎn)
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
