2023年8月5日每日一题--21. 合并两个有序链表

leetcode链接：21. 合并两个有序链表

题目分析

方案一

设置一个虚拟头节点，和一个临时节点：

虚拟头节点用于维护链表的头；
临时节点用于维护将要加入链表的前一个节点。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode temp = head;
        while (list1 != null || list2 != null) {
            if (list1 == null) {
                temp.next = list2;
                break;
            } else if (list2 == null) {
                temp.next = list1;
                break;
            } else {
                if (list1.val > list2.val) {
                    temp.next = list2;
                    temp = list2;
                    list2 = list2.next;
                } else {
                    temp.next = list1;
                    temp = list1;
                    list1 = list1.next;
                }
            }
        }

        return head.next;
    }
}

结果

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:40.5 MB,击败了42.37% 的Java用户

官方题解

https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/

方法一：递归

class Solution {
    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;
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：迭代

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。