链表：合并两个有序链表

题目：

给定两个有序单链表的头节点 head1 和 head2，请合并两个有序链表，合并后的链表依然有序，并返回合并后的头节点。

例如：

0->2->3->7->null

1->3->5->7->9->null

0->1->2->3->3->5->7->7->9->null

分析：

1. 如果某个链表为空，直接返回另一链表头节点即可。

2. 记录较小的头节点即为最后返回节点，记为 head。

3. 将cur1指向较小的头节点，另一个为cur2，遍历cur1和cur2，如果cur1的值不大于cur2则，cur1指向下一个节点，否则将cur1.next赋为cur2，cur2指向下一个节点，重新判断cur1的值与cur2的值的大小。

4. 最后将剩余的节点连接到新链表的后面

 1 public Node merge(Node head1, Node head2)
 2 {
 3     if(head1 == null || head2 == null)
 4         return head1 == null ? head2 : head1;
 5 
 6     Node head = head1.data < head2.data ? head1 : head2;
 7     Node cur1 = head == head1 ? head1 : head2;
 8     Node cur2 = head == head1 ? head2 : head1;
 9     Node pre = null, next = null;
10 
11     while(cur1 != null && cur2 != null)
12     {
13         if(cur1.data <= cur2.data)
14         {
15             pre = cur1;
16             cur1 = cur1.next;
17         }
18         else
19         {
20             next = cur2.next;
21             pre.next = cur2;
22             cur2.next = cur1;
23             pre = cur2;
24             cur2 = next;
25         }
26     }
27     pre.next = cur1 == null ? cur2 : cur1;
28     return head;
29 }

参考资料：程序员代码面试指南 IT名企算法与数据结构题目最优解，左程云