Sunday, September 15, 2013

Merge Two Sorted Lists

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