LeetCode 21. 合并兩個有序連結清單

題目描述

将兩個有序連結清單合并為一個新的有序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。

示例：

輸入：1->2->4, 1->3->4

輸出：1->1->2->3->4->4

思路

定義一個啞結點，逐個比較大小，将目前較小值結點p後面。

到後面較長的連結清單的多餘元素直接補上

具體代碼

/**
 * 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 dummy(0);
        ListNode* p = &dummy;
        while(l1&&l2){
            int val1 = l1->val;
            int val2 = l2->val;
            if(val1<val2){
                p->next = l1;
                p = l1;
                l1 = l1->next;
            }else{
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        if(l1){
            p->next = l1;
        }else if(l2){
            p->next = l2;
        }
        return dummy.next;
    }
};