归并排序 2016-8-4

[zhaokuohaha]

两列排序 21 : https://leetcode.com/problems/merge-two-sorted-lists/ k列排序 23 : https://leetcode.com/problems/merge-k-sorted-lists/

[SnackMen]

/*
*[AC]21. Merge Two Sorted Lists
*/
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode list = new ListNode(0);
        ListNode root=list;
        if(l1==null && l2==null)
            return null;
        while(l1!=null || l2!=null){
            ListNode temp=null;
            if(l1==null){
                temp=l2;
                l2=l2.next;
            }else if(l2==null){
                temp=l1;
                l1=l1.next;
            }else{
                if(l2.val<l1.val){
                    temp=l2;
                    l2=l2.next;
                }else{
                    temp=l1;
                    l1=l1.next;
                }
            }
            list.next=temp;
            list=list.next;
        }
        return root.next;

    }
}
/*附带人家的递归*/
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

[SnackMen]

/*
*[AC]23. Merge k Sorted Lists   分治法
*/
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0 || lists==null)
            return null;
        int n=lists.length;
        while(n>1){
            int k=(n+1)/2;
         for(int i=0;i<n/2;i++){
             lists[i]=mergeTwoLists(lists[i],lists[i+k]);
         }
         n=k;
        }
        return lists[0];
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode list = new ListNode(0);
        ListNode root=list;
        if(l1==null && l2==null)
            return null;
        while(l1!=null || l2!=null){
            ListNode temp=null;
            if(l1==null){
                temp=l2;
                l2=l2.next;
            }else if(l2==null){
                temp=l1;
                l1=l1.next;
            }else{
                if(l2.val<l1.val){
                    temp=l2;
                    l2=l2.next;
                }else{
                    temp=l1;
                    l1=l1.next;
                }
            }
            list.next=temp;
            list=list.next;
        }
        return root.next;

    }
}

[wolfogre]

// [AC] 21. Merge Two Sorted Lists
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        while(l1 != null || l2 != null){
            if(l1 == null || (l2 != null && l2.val < l1.val)){
                p.next = new ListNode(l2.val);
                p = p.next;
                l2 = l2.next;
            } else {
                p.next = new ListNode(l1.val);
                p = p.next;
                l1 = l1.next;
            }
        }
        return head.next;
    }
}

[dayang]

/**
 * [AC] LeetCode 21 Merge Two Sorted Lists
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    var head = p = new ListNode(0);
    while(l1 || l2){
        if(l1 === null ||(l2!==null && l1.val > l2.val)){
            p.next = l2;
            l2 = l2.next;
        }else if(l2 === null || l1.val <= l2.val){
            p.next = l1;
            l1 = l1.next;
        }
        p = p.next;
    }
    return head.next;
};

[zhaokuohaha]

21 - C# - 归并

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        ListNode L = new ListNode(0);
        ListNode head = L;
        while(l1 != null && l2 != null){
            L.next = new ListNode(Math.Min(l1.val, l2.val));
            L = L.next;
            if(l1.val < l2.val) l1 = l1.next;
            else l2 = l2.next;
        }
        while(l1 != null){
            L.next = new ListNode(l1.val);
            L = L.next;
            l1 = l1.next;
        }
        while(l2 != null){
            L.next = new ListNode(l2.val);
            L = L.next;
            l2 = l2.next;
        }
        return head.next;
    }
}

改良版

public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        ListNode L = new ListNode(0);
        ListNode head = L;
        while(l1 != null && l2 != null){
            L.next = new ListNode(Math.Min(l1.val, l2.val));
            L = L.next;
            if(l1.val < l2.val) l1 = l1.next;
            else l2 = l2.next;
        }
        L.next = l1 != null ? l1 : l2;
        return head.next;
    }
}

大幅改良版

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        ListNode L = new ListNode(0);
        ListNode head = L;
        while(l1 != null && l2 != null){
            //L.next = new ListNode(Math.Min(l1.val, l2.val));
            if(l1.val < l2.val) {
                L.next = l1;
                l1 = l1.next;
            }
            else {
                L.next = l2;
                l2 = l2.next;
            }
            L = L.next;
        }
        L.next = l1 != null ? l1 : l2;
        return head.next;
    }
}

[zhaokuohaha]

23 - C# - 分治?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        if(lists.Length==0) return null;
        if(lists.Length == 1 ) return lists[0];
        for(int i=1; i<lists.Length; i++){
            lists[0] = MergeTwoLists(lists[0],lists[i]);
        }
        return lists[0];
    }

    private ListNode MergeTwoLists(ListNode l1, ListNode l2) {
        ListNode L = new ListNode(0);
        ListNode head = L;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val) {
                L.next = l1;
                l1 = l1.next;
            }
            else {
                L.next = l2;
                l2 = l2.next;
            }
            L = L.next;
        }
        L.next = l1 != null ? l1 : l2;
        return head.next;
    }
}

[dayang]

/**
 * [AC] LeetCode 23 Merge k Sorted Lists
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    if (lists.length === 0) return null;
    if (lists.length === 1) return lists[0];
    function mergeTwoLists(l1, l2) {
        if(l1 === null) return l2;
        if(l2 === null) return l1;
        var head = new ListNode(0);
        var p = head;
        while (l1 || l2) {
            if (l1 === null || (l2 !== null && l1.val > l2.val)) {
                p.next = l2;
                l2 = l2.next;
            } else if (l2 === null || l1.val <= l2.val) {
                p.next = l1;
                l1 = l1.next;
            }
            p = p.next;
        }
        return head.next;
    }
    for (let i = 1; i < lists.length; i++) {
        lists[0] = mergeTwoLists(lists[0], lists[i]);
    }
    return lists[0];
};

[wolfogre]

用队列避免长度差异大的链表合并，当参加排序的链表的长度比较统一时，这样做的效率才比较可观。

/**
 * [AC] LeetCode 23 Merge k Sorted Lists
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        LinkedList<ListNode> queue = new LinkedList<ListNode>();
        for(ListNode n : lists){
            if(n != null)
                queue.add(n);
        }
        if(queue.size() == 0)
            return null;
        while(queue.size() >= 2){
            queue.add(mergeTwoLists(queue.poll(), queue.poll()));
        }
        return queue.poll();
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        while(l1 != null || l2 != null){
            if(l1 == null || (l2 != null && l2.val < l1.val)){
                p.next = new ListNode(l2.val);
                p = p.next;
                l2 = l2.next;
            } else {
                p.next = new ListNode(l1.val);
                p = p.next;
                l1 = l1.next;
            }
        }
        return head.next;
    }
}