有序链表合并与分治

一、面试常考点

1. 两两合并

使用 dummy + tail 指针构建新链表。

2. K 路合并

分治合并或最小堆。

二、细节介绍

1. 两链表合并

每次取较小节点接到尾部。

2. K 链表合并

分治复杂度可到 O(N log k)。

三、示例代码

function mergeTwoLists(l1, l2) {
  const dummy = { next: null }
  let tail = dummy

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      tail.next = l1
      l1 = l1.next
    } else {
      tail.next = l2
      l2 = l2.next
    }
    tail = tail.next
  }

  tail.next = l1 || l2
  return dummy.next
}

四、常用应用场景

1. 多路数据流归并

日志流、增量数据归并。

2. 外排序子过程

归并排序中的链表版本。