[LeetCode]21.Merge Two Sorted Lists

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
字数统计：364 字 | 阅读时长：2 分钟

21. Merge Two Sorted Lists

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

给定有序的两个数组，合并两个数组，并保持有序。
这其实是归并排序的其中一个步骤。

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
/**
 * 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) {
        if(l1 == NULL && l2 == NULL) return NULL;
        if(l1 == NULL && l2 != NULL) return l2;
        if(l1 != NULL && l2 == NULL) return l1;
        
        ListNode* result;
        
        if (l1->val <= l2->val) {
            result = l1;
            l1 = l1->next;
            result->next = mergeTwoLists(l1, l2); 
        } else {
            result = l2;
            l2 = l2->next;
            result->next = mergeTwoLists(l1, l2); 
        } 
        return result;
    }
};

tip:

  1. 两个参数是否空指针需要判断

result

提交过程错了两次，一次是因为空指针，一次是因为判断大小的语句里，还多余判断了一次下一个元素是不是空指针，导致少了个元素。

Runtime: 20 ms, faster than 9.56% of C++ online submissions for Merge Two Sorted Lists.
Memory Usage: 9.9 MB, less than 88.65% of C++ online submissions for Merge Two Sorted Lists.

内存占用太大，还有改进空间。

有个疑惑，其中一段代码改成以下这样后，内存占用竟然升高到10.1M

1
2
3
4
5
6
7
if (l1->val <= l2->val) {
    result = l1;
    result->next = mergeTwoLists(l1->next, l2); 
} else {
    result = l2;
    result->next = mergeTwoLists(l1, l2->next); 
}