Fork me on GitHub

leetcode之21. 合并两个有序链表

发表于 | 分类于
字数统计 284 字 | 阅读时长 1 分钟

题目描述：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

1
2
3
> 输入：1->2->4, 1->3->4
> 输出：1->1->2->3->4->4
>

解题思路：

思路一：

非递归，时间复杂度：$Q(n)$，空间复杂度：$O(n)$.

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
35
36
37
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *p = new ListNode(0);
        ListNode *q = p;
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;

        while(l1 != NULL && l2 != NULL)
        {
          if(l1->val < l2->val)
          {
            p -> next = l1;
            p = p->next;
            l1 = l1->next; 
          }
          else
          {
            p -> next = l2;
            p = p->next;
            l2 = l2->next;
          }
          if(l1 == NULL)
          {
            p->next = l2;
          }
          if(l2 == NULL)
          {
            p->next = l1;
          }
        }
        
        return q->next;
    }
};

思路二：

递归，时间复杂度： $O(n)$, 空间复杂度：$O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *p = NULL;
        if(l1 == NULL)
            return l2;
        else if(l2 == NULL)
            return l1;
        else if(l1->val < l2->val)
        {
            p = l1;
            p->next = mergeTwoLists(l1->next, l2); 
        }
        else
        {
            p = l2;
            p->next = mergeTwoLists(l1, l2->next);
        }
        
        return p;
    }
};