LeetCode.021.Merge Two Sorted Lists 合并两个有序链表

题目描述

021 Merge Two Sorted Lists
https://leetcode-cn.com/problems/merge-two-sorted-lists/

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

---

相似题目

归并排序问题
LeetCode.021.Merge Two Sorted Lists 合并两个有序链表
LeetCode.023.Merge k Sorted Lists 合并K个排序链表

---

解题过程

2020迭代

时间复杂度 O(n+n)，空间复杂度O(1)

private static class SolutionV2020 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode dumbHead = new ListNode(0);
        ListNode k = dumbHead;
        while (l1 != null || l2 != null) {
            if ((l1 != null && l2 != null && l1.val < l2.val) || l2 == null) {
                k.next = l1;
                k = l1;
                l1 = l1.next;
            } else {
                k.next = l2;
                k = l2;
                l2 = l2.next;
            }
        }
        return dumbHead.next;
    }
}

2018迭代

这是之前做过的一道题，非常简单，也没啥注意事项，写完一次AC，调都不用调：

private static class SolutionV2018 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode p1 = l1, p2 = l2, res, resHead;
        if (p1.val < p2.val) {
            resHead = res = p1;
            p1 = p1.next;
        } else {
            resHead = res = p2;
            p2 = p2.next;
        }
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                res.next = p1;
                p1 = p1.next;
            } else {
                res.next = p2;
                p2 = p2.next;
            }
            res = res.next;
        }
        res.next = p1 == null ? p2 : p1;
        return resHead;
    }
}

递归

讨论区排第一位的是一个递归解法，代码很简洁：

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

}

不过评论中好几个说有栈溢出风险。

---

GitHub代码

algorithms/leetcode/leetcode/_021_MergeTwoSortedLists.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_021_MergeTwoSortedLists.java

---