。。。剑指Offer之——合并两个排序的链表。。。
1 public ListNode Merge(ListNode list1, ListNode list2) { 2 // list1，list2中，只要有一个是空的，则返回另外一个链表 3 if (list1 == null) { 4 return list2; 5 } 6 if (list2 == null) { 7 return list1; 8 } 9 // 新建一个链表 10 ListNode k = new ListNode(Integer.MIN_VALUE); 11 // 新建一个头指针，指向新建的链表 12 ListNode head = k;//k其实是用来迭代合并之后的链表 13 // p指针用来迭代list1，q指针用来迭代list2 14 ListNode p = list1, q = list2; 15 while (p != null && q != null) { 16 // 哪一个值小，k就指向谁 17 if (p.val > q.val) { 18 k.next = q; 19 k = q; 20 q = q.next;//往后移动 21 } else { 22 k.next = p; 23 k = p; 24 p = p.next;//往后移动 25 } 26 } 27 // 最终如果q提前结束（q==null），p不为空，则直接把p挂到k的后面 28 if (p != null) { 29 k.next = p; 30 } 31 // 最终如果q提前结束（p==null），q不为空，则直接把q挂到k的后面 32 if (q != null) { 33 k.next = q; 34 } 35 // 真正的头节点是原来新建k节点的下一个节点，因为k是新建的节点， 36 // 合并之后，k节点其实不属于最终合并之后的链表 37 return head.next; 38 }
更多精彩
