合并兩個排序的連結清單（C++簡單區）

合并兩個排序的連結清單

題目：輸入兩個遞增排序的連結清單，合并這兩個連結清單并使新連結清單中的節點仍然是遞增排序的。

示例1：

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

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

限制：

0 <= 連結清單長度 <= 1000

解題思路

一開始的思路是将l2上的節點一個個拆下來與l1各個節點的值進行比對，然後以此方法将l2節點全部按大小順序插入到l1中，最後傳回l1。

代碼如下：

/**
 * 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* q=l1,*p=l2,*r=l1;
       while(l2)
       {
           p=l2->next;
           l2->next=NULL;
           while(q && q->val<l2->val)
           {
               r=q;
               q=q->next;
           }
           l2->next=q;
           r->next=l2;
           q=l1;
           l2=p;
       }
       return l1;
    }
};
           

結果展示

是以又換了一種方法。這種方法與排序算法中的歸并排序算法一緻，這裡是将兩個有序的連結清單歸并到另一個新連結清單中，使之依然有序。

算法流程:

1.初始化:僞頭節點dum,節點res指向dum。

2.循環合并:當l1 或l2為空時跳出;

1. 當l1->val < l2->val時: res的後繼節點指定為l1，并l1向前走一 步;
2. 當l1->val ≥ l2->val 時: res的後繼節點指定為l2 ,并l2向前走一步;
3. 節點res向前走一步,即res = res->next。

3.合并剩餘尾部:跳出時有兩種情況， 即l1為空或l2為空。

1. 若l1≠null :将l1添加至節點res之後;
2. 否則:将l2 添加至節點res之後。

4.傳回值:合并連結清單在僞頭節點 dum之後，是以傳回dum->next即啊。

連結：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/solution/mian-shi-ti-25-he-bing-liang-ge-pai-xu-de-lian-b-2/

代碼展示

代碼如下：

/**
 * 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) return l2;
        if(l2==NULL) return l1;
        ListNode* dum=new ListNode(0);
        ListNode* res=dum;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                res->next=l1;
                l1=l1->next;
            }
            else
            {
                res->next=l2;
                l2=l2->next;
            }
            res=res->next;
        }
        res->next=l1?l1:l2;
        return dum->next;
    }
};