LeetCode 21. Merge Two Sorted Lists

Problem

LeetCode 21. Merge Two Sorted Lists

1. 题目简述

合并两个有序链表。例如：

Example:

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

2. 算法思路

参考解法：花花酱LeetCode

极其经典的老题目，每年肯定都有考的，背下来就可以了。进阶版本：LeetCode 23. Merge k Sorted Lists

递归

当两个list有一个为空时，直接返回另一个。如果都不为空，比较两个list队首的值，选其中较小的那个，我们设为node，将该node.text设为node.next和另一个List的merge结果即可，返回node节点。

时间复杂度:O(m + n)，最坏情况m+n次递归，每次O(1)。

空间复杂度:O(m + n)，递归的最坏情况是二者之和。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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;
        }
    }
}

循环

思路基本一致，只是需要注意其中一个为空的时候的情况。

时间复杂度:O(m + n)，最坏情况m+n次递归，每次O(1)。

空间复杂度:O(1)，不需要额外空间，merge都是直接操作指针的，没有新建链表。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode ptr = head;

        while (l1 != null && l2 != null) {
            int value1 = l1.val, value2 = l2.val;
            if (value1 <= value2) {
                ptr.next = l1;
                l1 = l1.next;
                ptr = ptr.next;
            } else {
                ptr.next = l2;
                l2 = l2.next;
                ptr = ptr.next;
            }
        }

        ptr.next = l1 == null ? l2 : l1;

        return head.next;
    }
}