Q:
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.
A:
这个很简单,直接就过了。 嗯,除了有个else 少写了l, 还有就是开始忘了return l3;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// Start typing your Java solution below
// DO NOT write main() function
ListNode l3;
ListNode justAddedNode; // p1 are the currentPointer to Node on l1;
if(l1 == null){
l3=l2;
return l3;
}else if(l2 == null){
l3 = l1;
return l3;
}else{ // we need define the returend value
if(l1.val < l2.val){
l3 = l1;
l1 = l1.next;
}else{
l3 = l2;
l2 = l2.next;
}
}
justAddedNode = l3;
//now that both list are not null
while(l1!=null && l2!= null){
if(l1.val < l2.val){
justAddedNode.next = l1;
l1 = l1.next;
justAddedNode = justAddedNode.next;
}else{
justAddedNode.next = l2;
l2 = l2.next;
justAddedNode = justAddedNode.next;
}
}
//now l1 or l2 is null
if(l1 == null){
justAddedNode.next = l2;
}else{
justAddedNode.next = l1;
}
return l3;
}
}
----------------------------第二遍用了header , 这样更简单些。 明显地比第一遍进步许多-------
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode header1 = new ListNode(0);
header1.next = l1;
ListNode header2 = new ListNode(0);
header2.next = l2;
ListNode header3 = new ListNode(0);
ListNode tail = header3;
ListNode tmp;
while(header1.next!=null && header2.next!=null){
if(header1.next.val <= header2.next.val){
// detach first in list 1
tmp = header1.next;
header1.next = header1.next.next;
}else{
// detach first in list 1
tmp = header2.next;
header2.next = header2.next.next;
}
tail.next = tmp;
tail = tail.next;
}
if(header1.next != null){
tail.next = header1.next;
}else{
tail.next = header2.next;
}
return header3.next;
}
}
------------------------3 rd Pass ----------------list1 和list 2 是不需要header的--------
思路和 第二遍 一样
* Definition for singly-linked list.
/* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode header = new ListNode(Integer.MIN_VALUE);
ListNode tail = header;
ListNode tmp;
while(l1!=null && l2!=null){
if(l1.val<l2.val){
tmp = l1;
l1 = l1.next;
}else{
tmp = l2;
l2 = l2.next;
}
tail.next = tmp;
tail = tail.next;
}
if(l1 == null)
tmp = l2;
else
tmp = l1;
tail.next = tmp;
return header.next;
}
}
No comments:
Post a Comment