合并两个有序链表-迭代

孙泽辉

发布于：2021年8月25日

字数：631字

时长：2分钟

次浏览

学数据结构的时候碰到一题合并链表，果不其然在LeetCode上有个几乎一样的题目，正好！

题目

LeetCode上的

21. 合并两个有序链表

难度 简单

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

课本中的

假设有两个按元素值递增有序排列的且带头结点的单链表A和表B，请编写算法将表A和表B合并成一个按元素值递减有序排列的单链表C，并要求利用原表（即表A或表B）的节点空间存放表C

题解

LeetCode和课本上的区别就是课本上说了不准用辅助空间，相对难一点。

LeetCode解法

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let merged: ListNode = new ListNode();
    const m = merged;
    while (l1 !== null && l2 !== null) {
        if (l1?.val <= l2.val) {
            merged.next = l1
            l1 = l1.next;
        } else {
            merged.next = l2;
            l2 = l2.next
        }
        merged = merged.next
    }
    merged.next = l1 === null ? l2 : l1;
    return m.next;
}

新建了个辅助节点，看A链表和B链表节点的值哪个小，从小到大依次链到辅助节点上（类似归并排序）

最后因为一定会有个剩下的节点，将next指向他；因为第一个节点的值是空的，返回第一个以后的节点

课本解法

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null) {
    let merged: ListNode = l1 as ListNode;
    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            let t = l1.next
            l1.next = merged.next;
            merged.next = l1;
            l1 = t
        } else {
            let t = l2.next
            l2.next = merged.next;
            merged.next = l2;
            l2 = t
        }
    }
    while (l1 !== null) {
        let t = l1.next
        l1.next = merged.next;
        merged.next = l1;
        l1 = t
    }
    while (l2 !== null) {
        let t = l2.next
        l2.next = merged.next;
        merged.next = l2;
        l2 = t
    }
}

因为不让用辅助空间，所以以链表A为合并后的链表，根据表A和表B的数据域大小选择将哪个节点插入到合并后的链表上，然后将其指针指向最新的位置

但是这种方式就找不到合并后的链表头指针了（或许是我菜）

总结

数据结构真好玩