筆試題34. LeetCode OJ (21)

已經已連續做了好幾道題了，感覺停不下來了，突然來了興趣了，這個題讓我覺得思路很清晰，合並兩個排序的鏈表。我的思路如下：分別從兩個鏈表裡面摘取節點放到新的鏈表中，最後摘到一個也不留就行了。不過需要注意的是一些小細節，主要的注意事項如下：

1.兩空（兩個空的鏈表）

2.一空（一個鏈表為空一個部位空）

3.一個摘完了，另外的可能還有節點（這個需要好好注意一下，很容易出錯的）

好了，見代碼吧：

/**
 * 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) 
    {
        //類似於從兩個鏈表上取下節點，放到newHead中去
        if(l1 == NULL && l2 == NULL)
        {
            return NULL;
        }
        if(l1 == NULL)
        {
            return l2;
        }
        if(l2 == NULL)
        {
            return l1;
        }
        
        ListNode * newHead=NULL;
        if(l1->val <= l2->val)
        {
            newHead=l1;
            l1=l1->next;
        }
        else
        {
             newHead=l2;
             l2=l2->next;
        }
        newHead->next = NULL;
        ListNode *cur = newHead;
        while(l1 && l2)
        {
            if(l1->val <= l2->val)
            {
                cur->next = l1;
                l1=l1->next;
            }
            else
            {
                cur->next = l2;
                l2 = l2->next;
            }
            cur=cur->next;
            cur->next=NULL;
        }
        
        if(l1)
        {//說明 l2 完了，只剩 l1 了
            cur->next = l1;    
        }
        if(l2)
        {//說明 l1 完了，只剩 l2 了
            cur->next=l2;
        }
        
        return newHead;
    }
};