[LeetBook] Merge every two List use [Merge Two Sorted Lists] code.


  • 0
    V

    You will find more Chinese explaination in this open source book LeetBook

    Remember the problem of Merge Two Sorted Lists? We can use it's code to solve this problem through adding few more line.

    if lists.length is even :
    enter image description here

    if lists.length is odd:

    enter image description here

    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists.length == 0)
                return null;
            //control the step
            for(int step = 1;step < lists.length;step*=2)
                //merge two list every one step
                for(int i = 0;i < lists.length;i+=step*2)
                {
                    if(i+step >= lists.length) break;
                    lists[i] = mergeTwoLists(lists[i],lists[i+step]);
                }
            return lists[0];
        }
        //the code of merge Two Lists
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode result = new ListNode(0);
            ListNode tmp = result;
            while(l1 != null || l2 != null)
            {
                if(l2 == null || (l1 != null && l1.val <= l2.val))
                {
                    tmp.next = l1;
                    l1 = l1.next;
                }
                else 
                {
                    tmp.next = l2;
                    l2 = l2.next;
                }
                tmp = tmp.next;
            }
            return result.next;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.