合并两个排序的链表
思路
题解
package swordPointingToTheOffer;
//public class ListNode {
// int val;
// ListNode next;
// ListNode(int x) { val = x; }
//}
public class TwentyFive {
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode perHead = new ListNode(0);
ListNode move = perHead;
boolean isFirst = true;
while (l1!=null&&l2!=null){
if(l1.val>l2.val){
ListNode temp = new ListNode(l2.val);
move.next = temp;
move = move.next;
l2=l2.next;
}else {
ListNode temp = new ListNode(l1.val);
move.next= temp;
move = move.next;
l1 = l1.next;
}
}
if(l1==null){
move.next = l2;
}else if(l2==null){
move.next = l1;
}
return perHead.next;
}
public static void main(String[] args) {
ListNode listNode11 = new ListNode(1);
ListNode listNode12 = new ListNode(3);
ListNode listNode13 = new ListNode(5);
ListNode listNode14 = new ListNode(7);
listNode11.next = listNode12;
listNode12.next = listNode13;
listNode13.next = listNode14;
ListNode listNode21 = new ListNode(2);
ListNode listNode22 = new ListNode(4);
ListNode listNode23 = new ListNode(6);
ListNode listNode24 = new ListNode(8);
listNode21.next = listNode22;
listNode22.next = listNode23;
listNode23.next = listNode24;
ListNode res = mergeTwoLists(listNode11,listNode21);
while (res!=null){
System.out.println(res.val);
res = res.next;
}
}
}
优化内存空间
新链表其实不用每次新建节点,让指针指向两链表中的值就行。。
package swordPointingToTheOffer;
//public class ListNode {
// int val;
// ListNode next;
// ListNode(int x) { val = x; }
//}
public class TwentyFive {
//其实不用每次新建节点,代码如下
public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
ListNode merge = new ListNode(0);
ListNode temp = merge;
while (l1!=null && l2!=null){
if(l1.val< l2.val){
//直接指向l1链表中的节点
temp.next = l1;
l1 = l1.next;
}else {
//直接指向l2链表中的节点
temp.next = l2;
l2 = l2.next;
}
//工作指针后移
temp = temp.next;
}
//最后把尾部的添加
if(l1==null){
temp.next = l2;
}else if(l2==null){
temp.next = l1;
}
return merge.next;
}
public static void main(String[] args) {
ListNode listNode11 = new ListNode(1);
ListNode listNode12 = new ListNode(3);
ListNode listNode13 = new ListNode(5);
ListNode listNode14 = new ListNode(7);
listNode11.next = listNode12;
listNode12.next = listNode13;
listNode13.next = listNode14;
ListNode listNode21 = new ListNode(2);
ListNode listNode22 = new ListNode(4);
ListNode listNode23 = new ListNode(6);
ListNode listNode24 = new ListNode(8);
listNode21.next = listNode22;
listNode22.next = listNode23;
listNode23.next = listNode24;
ListNode res = mergeTwoLists2(listNode11,listNode21);
while (res!=null){
System.out.println(res.val);
res = res.next;
}
}
}