Leetcode-21 —— Merge two sorted lists

Description

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

分析

合并两个有序链表，合并后的链表也应是有序的，而且重复元素不去重

假设有 a, b 两个链表，考虑以下 corner case:

• 其中一个链表为 null
• a 的末尾元素大于 b 的首元素
• a 的元素个数比 b 多

常规的解法就是遍历两个列表，为新生成的链表维护一个头指针 dummyHead 和一个滑动指针cur，另外分别为两个给定的链表维护一个指针，假设为 a, b，按如下规则遍历

1. 初始化 dummyHead 和 cur， 让 dummyHead = cur
2. 初始化 a, b 分别指向两个链表的头节点
3. 比较 a, b ，让小的一个节点作为 cur 的 next 节点，并且指针向后移动一位, cur 同样向后移动一位
4. 重复 3，直到 a, b 两个指针之一为空
5. 如果 a, b 中还有非空指针，让其作为 cur 的 next 节点
6. 返回 dummyHead 的 next 节点

程序设计

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode(0);
        ListNode dummyHead = cur;
        
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            
            cur = cur.next;
        }
        
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        
        return dummyHead.next;
    }
}

值得注意的是，此处采用 dummyHead 作为新链表的头节点，最终返回了 dummyHead.next，这样做（比起先比较 L1 和 L2 的头节点然后选中较小者作为新链表的头节点）将特殊问题一般化，减少了特殊逻辑的处理，是很值得学习的一种思路。

如上代码，提交后运行时 0 ms, 打败 100% 的提交。

其他解法

• 递归解法