# Merge Two Sorted Lists

## Question

### Problem Statement

Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.

#### 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;
}
};


### Java

/**
* Definition for ListNode.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int val) {
*         this.val = val;
*         this.next = null;
*     }
* }
*/
public class Solution {
/**
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;

while ((l1 != null) && (l2 != null)) {
if (l1.val > l2.val) {
curr.next = l2;
l2 = l2.next;
} else {
curr.next = l1;
l1 = l1.next;
}
curr = curr.next;
}

curr.next = (l1 != null) ? l1 : l2;

return dummy.next;
}
}


### 源码分析

1. 异常处理，包含在dummy->next中。
2. 引入dummycurr节点，此时curr指向的节点为dummy
3. 对非空l1,l2循环处理，将l1/l2的较小者链接到curr->next，往后递推curr
4. 最后处理l1/l2中某一链表为空退出while循环，将非空链表头链接到curr->next
5. 返回dummy->next，即最终的首指针

Note 链表的合并为常用操作，务必非常熟练，以上的模板非常精炼，有两个地方需要记牢。1. 循环结束条件中为条件与操作；2. 最后处理curr->next指针的值。