vvrf / DSA.log

问题拆解

两个升序链表 l1、l2，要拼成一个新的升序链表。因为两边都已经有序，每一步只需要比较两个表头，把更小的那个接到结果后面，然后让它往后走一格。

麻烦的是结果链表的第一个节点：它没有前驱，接第一个节点和接后面的节点得写两套逻辑。如果每次都判断“结果是不是空的”，代码会被这个边界搞得很啰嗦。

引入一个不存放数据的哨兵（dummy）节点当作结果的假头，所有真实节点都变成“接在某个节点后面”，第一个节点的特殊情况就消失了。

迭代：哨兵 + 尾指针

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode();
    ListNode tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            tail.next = l1;
            l1 = l1.next;
        } else {
            tail.next = l2;
            l2 = l2.next;
        }
        tail = tail.next;
    }
    tail.next = l1 != null ? l1 : l2;
    return dummy.next;
}

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    tail = dummy
    while l1 and 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 if l1 else l2
    return dummy.next

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            tail.Next = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            l2 = l2.Next
        }
        tail = tail.Next
    }
    if l1 != nil {
        tail.Next = l1
    } else {
        tail.Next = l2
    }
    return dummy.Next
}

pub fn merge_two_lists(
    mut l1: Option<Box<ListNode>>,
    mut l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    let mut dummy = Box::new(ListNode::new(0));
    let mut tail = &mut dummy;
    while l1.is_some() && l2.is_some() {
        let source = if l1.as_ref().unwrap().val <= l2.as_ref().unwrap().val {
            &mut l1
        } else {
            &mut l2
        };
        let mut node = source.take().unwrap();
        *source = node.next.take();
        tail.next = Some(node);
        tail = tail.next.as_mut().unwrap();
    }
    tail.next = l1.or(l2);
    dummy.next
}

tail 始终指向结果链表的最后一个节点，每次把较小的节点挂上去后往前移。循环结束时至少有一条链表走空，剩下那条已经是有序的尾巴，直接整段接上即可。最后返回 dummy.next，跳过那个假头。

用 <= 而不是 < 能保证相等时优先接 l1，合并是稳定的。

递归

也可以顺着定义来递归：两个头里较小的那个，它的 next 就是“剩下的部分继续合并”的结果。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
}

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val <= l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    l2.next = mergeTwoLists(l1, l2.next)
    return l2

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    if l1.Val <= l2.Val {
        l1.Next = mergeTwoLists(l1.Next, l2)
        return l1
    }
    l2.Next = mergeTwoLists(l1, l2.Next)
    return l2
}

pub fn merge_two_lists(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    match (l1, l2) {
        (None, rest) | (rest, None) => rest,
        (Some(mut a), Some(mut b)) => {
            if a.val <= b.val {
                a.next = Self::merge_two_lists(a.next.take(), Some(b));
                Some(a)
            } else {
                b.next = Self::merge_two_lists(Some(a), b.next.take());
                Some(b)
            }
        }
    }
}

写法很短，但递归深度等于两链表总长，节点多时不如迭代稳。

复杂度

指标	复杂度	原因
时间	`O(m + n)`	每个节点被接入结果一次
空间	`O(1)` / `O(m + n)`	迭代只用哨兵与指针；递归的栈深与总长度相同

可以迁移的模式

链表结果需要从零构建时，先设一个 dummy 头，省掉首节点判空；
“比较两个表头、取小的、推进”是归并排序合并步骤的原型；
收尾时利用“另一条已经有序”直接整段拼接，不用逐个搬。

合并两个有序结构这件事在数组、链表、外部排序里反复出现，哨兵是让代码变干净的常用手法。