MergeList

发表于 分类于

题目描述[原题链接][acwing.com/problem/content/description/34/]

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

样例

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

输出：1->2->3->4->5->5

算法分析

建一个傻瓜节点，防止全空，判断当前链表的值大小，将小值接在链表的新链表，自身后移，直到有一个链表空，最后将不空的链表接在新链表，结束

C++代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if(l1==NULL)return l2;
        if(l2==NULL)return l1;
        
        auto dummy = new ListNode(-1);
        auto p = dummy;
        while(l1&&l2){
            if(l1->val>=l2->val){
                p->next = l2;
                l2 = l2->next;
            }else {
                p->next = l1;
                l1 = l1->next;
            }
            p=p->next;
        }
        p->next = l1==NULL?l2:l1;
        return dummy->next;
    }  
};

Java代码

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        while(l1!=null&&l2!=null){
            if(l1.val>=l2.val){
                p.next = l2;
                l2=l2.next;
            }else{
                p.next = l1;
                l1 = l1.next;
            }
            p=p.next;
        }
        p.next = l1!=null?l1:l2;
        return dummy.next;
    }
}