思想
类似于归并排序的合并两个排序的数组
代码
package linkList;
/**
* 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.+
* Input: 1->2->4, 1->3->4
* Output: 1->1->2->3->4->4
* Created by liqiushi on 2018/1/8.
*/
public class MergeTwoLists {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode rptr = result;
ListNode pptr = l1;
ListNode qptr = l2;
//遍历l1、l2
while (pptr != null && qptr != null) {
if (pptr.val <= qptr.val) {
rptr.next = pptr;
pptr = pptr.next;
} else {
rptr.next = qptr;
qptr = qptr.next;
}
rptr = rptr.next;
}
if(pptr!=null){
rptr.next = pptr;
}else{
rptr.next = qptr;
}
/* while (pptr == null && qptr != null) {
ListNode tmpNode = new ListNode(qptr.val);
rptr.next = tmpNode;
rptr = rptr.next;
qptr = qptr.next;
}
while (qptr == null && pptr != null) {
ListNode tmpNode = new ListNode(pptr.val);
rptr.next = tmpNode;
rptr = rptr.next;
pptr = pptr.next;
}*/
//若其中一个队列遍历完毕
return result.next;
}
}
