Task

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

1
2

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

Solution

  • 用两个指针分别遍历两个链表，取最小者放进结果链表尾部
  • 当走到某个输入链表的尾部时终止循环，并将另一个链表剩余部分（若存在）直接放进结果链表尾部
  • 时间复杂度：遍历一次，O(n)
  • 空间复杂度：只用了指针和dummy节点，O(1)
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// Runtime: 4 ms, faster than 97.91% of C++ online submissions for Merge Two Sorted Lists.
// Memory Usage: 14.5 MB, less than 5.74% of C++ online submissions for Merge Two Sorted Lists.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //建立dummy节点和添加结果用的tail指针
        ListNode *dummy=new ListNode;
        ListNode *tail=dummy;
        //当两个链表都未走到头时，比较两个节点
        while(l1 && l2){
            //保证l1节点比l2节点小
            if(l1->val > l2->val) swap(l1,l2);
            //将更小的节点放入结果链表中，继续走
            tail->next=l1;
            tail=tail->next;
            l1=l1->next;
        }
        //循环终止时可能有一个链表尾部非空，直接放到结果后面
        tail->next=l1?l1:l2;
        return dummy->next;
    }
};