题解 | #合并两个排序的链表#
合并两个排序的链表
http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode list3 = new ListNode(0);//注意节点值为0，该点类似于头指针。
ListNode head = list3;
//建立一个新表的头结点，注意同时要建一个类似于哨兵的节点始终指向新表头结点 //因为随着新表头节点遍历，是一去不复返的，如果不创立指向头结点的节点，会无法返回新链表 while (list1 != null && list2 != null) {//如果当前节点同时不为空，则进行比较 if (list1.val >= list2.val) { //通过对比，较小的连接到新表头节点 list3.next = list2;
list2 = list2.next;
list3 = list3.next;
} else {
list3.next = list1;
list1 = list1.next;
list3 = list3.next;
}
}
//以上新表头结点哨兵head不动，list1,2,3遍历。
if (list1 != null) {
list3.next = list1;
}
if (list2 != null) {
list3.next = list2;
}
return head.next;//这里一定要注意加next，因为他是哨兵(头指针)，他指的位置(head=list3)其实是不该有数据的。
}
}