0%

LeetCode 21. Merge Two Sorted Lists

Posted on In

题目

原题在此
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: l1 = [], l2 = []
Output: []

Example 3:
Input: l1 = [], l2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both l1 and l2 are sorted in non-decreasing order.

分析

当l1, l2均未遍历完时,依次链接值较小的node.之后将剩余的list全部接上.
非常简单的一道题,适合拿来练手一门不熟悉的语言.

代码

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
33
34
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(INT_MIN);
        ListNode* foo = &head;
        while(l1 && l2) {
            if(l1 -> val < l2 -> val) {
                foo -> next = l1;
                foo = foo -> next;
                l1 = l1 -> next;
            } else {
                foo -> next = l2;
                foo = foo -> next;
                l2 = l2 -> next;
            }
        }
        
        if(l1) {
            foo -> next = l1;
        } else {
            foo -> next = l2;
        }
        return head.next;
        
    }
};