# Merge Two Sorted Lists

## Question

Merge two sorted linked lists and return it as a new list.
The new list should be made by splicing together the nodes of the first two lists.

Example
Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null

## 題解

### C++

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0);
ListNode *lastNode = dummy;
while ((NULL != l1) && (NULL != l2)) {
if (l1->val < l2->val) {
lastNode->next = l1;
l1 = l1->next;
} else {
lastNode->next = l2;
l2 = l2->next;
}

lastNode = lastNode->next;
}

// do not forget this line!
lastNode->next =  (NULL != l1) ? l1 : l2;

return dummy->next;
}
};

### 源碼分析

1. 異常處理，包含在dummy->next中。
2. 引入dummylastNode節點，此時lastNode指向的節點為dummy
3. 對非空l1,l2循環處理，將l1/l2的較小者鏈接到lastNode->next，往後遞推lastNode
4. 最後處理l1/l2中某一鏈表為空退出while循環，將非空鏈表頭鏈接到lastNode->next
5. 返回dummy->next，即最終的首指標

Note 鏈表的合併為常用操作，務必非常熟練，以上的模板非常精煉，有兩個地方需要記牢。1. 循環結束條件中為條件與操作；2. 最後處理lastNode->next指標的值。