I have a pretty good MergeSort method. Can anyone speed up the run time or reduce the memory usage?


  • 95
    P
    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            ListNode f = head.next.next;
            ListNode p = head;
            while (f != null && f.next != null) {
                p = p.next;
                f =  f.next.next;
            }
            ListNode h2 = sortList(p.next);
            p.next = null;
            return merge(sortList(head), h2);
        }
        public ListNode merge(ListNode h1, ListNode h2) {
            ListNode hn = new ListNode(Integer.MIN_VALUE);
            ListNode c = hn;
            while (h1 != null && h2 != null) {
                if (h1.val < h2.val) {
                    c.next = h1;
                    h1 = h1.next;
                }
                else {
                    c.next = h2;
                    h2 = h2.next;
                }
                c = c.next;
            }
            if (h1 != null)
                c.next = h1;
            if (h2 != null)
                c.next = h2;
            return hn.next;
        }
    }

  • -10
    G
    This post is deleted!

  • 8
    X

    The algorithm includes recursion which consumes the stack memory, it seems that the stack memory usage is not constant. I can use the bottom-up merge sort to reduce memory.


  • 0
    S

    u r so creative.


  • 0
    Z

    good solution, easy to understand


  • 3

    Nice solution.

    I guess after the loop you can use this to make it even shorter

    c.next = (h1 !=null) ? h1 : h2;
    

    Here is my AC solution written in javascript

    var sortList = function(head) {
        if (!head || !head.next) return head;
        var fast = head.next.next;
        var slow = head;
        while (fast && fast.next) {
            fast = fast.next.next;
            slow = slow.next;
        }
    
        var head1 = sortList(slow.next);
        slow.next = null;
        var head2 = sortList(head);
        return mergeList(head1, head2);
    };
    
    var mergeList = function(h1, h2) {
        var dummy = new ListNode(null);
        var tail = dummy;
        while (h1 && h2) {
            if (h1.val <= h2.val) {
                tail = tail.next = h1;
                h1 = h1.next;
            } else {
                tail = tail.next = h2;
                h2 = h2.next;
            }
        }
        tail.next = h1 ? h1 : h2;
        return dummy.next;
    };

  • 0
    K
    ListNode f = head.next.next;
    ListNode p = head;
    

    Why is it that I get a stackoverflow when I initialize both f and p to head?


  • 0
    E
    This post is deleted!

  • 3
    W

    Space complexity of the solution is not O(1), but O(nlogn). However, it's very beautiful.


  • -3
    Z

    need to delete hn to avoid memory leak


  • 0
    H

    @kevinhsu same problem here, don't know the difference between

    ListNode f = head.next.next; 
    

    and

    ListNode f = head;
    

    Pls let me know you figured it out.


  • 2
    S

    I would say it's probably the case where you have only 2 inputs, say 2->1-> null;
    After the while loop, you end up getting p points to 1. Then you sort p.next (null), which won't do anything. After that you sort 2->1->null again. Stack overflow


  • 12
    D

    I suggest that by mentioning "Constant space" complexity, we should not use Recursion, which uses stack for each recursively called function.

    Thus you can simply use Iteration for merge sort.


  • 7
    B

    I think space complexity is O(logn), rather than O(nlogn)


  • 0
    R

    I guess the only way to reduce space cost is to avoid to use recursion. All recursive algorithms can be implemented iteratively. But iterative code could be so complex :(


  • 0
    Z

    In your code

            if (head == null || head.next == null)
                return head;
            ListNode f = head.next.next;
            ListNode p = head;
            while (f != null && f.next != null) {
                p = p.next;
                f =  f.next.next;
            }
            ListNode h2 = sortList(p.next);
            p.next = null;
            return merge(sortList(head), h2);
    

    if the linkList have two element {1,2}

    then p.next already is null then h2 is null

    sortList(head) still have two . the recursive will not ended.

    here is my code:

            if(!head || !head->next)
                return head;
    
            ListNode* slow = head;
            ListNode* fast = head;
            while(fast && fast->next)
            {
                slow = slow->next;
                fast = fast->next->next;
            }
            ListNode* head2 = slow->next;
            slow->next = NULL;//把两条链表割断
            ListNode* p1;
            ListNode* p2;
            if(!head2)  //注意两个元素的 情况
            {
                head->next = NULL;
                p1 = sortList(head);
                p2 = sortList(slow);
            }
            else
            {
                p1 = sortList(head);
                p2 = sortList(head2);
            }
    
            return MergeList(p1,p2);
    

  • 0
    E

    Well, you didn't notice he initialize ListNode f = head.next.next; rather than just head. This well solve the problem of two elements.


  • 0
    A

    rewrite CPP version

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(head==NULL || head->next==NULL)  return head;
            ListNode *h1 = head;
            ListNode*h2 = head->next->next;
            while(h2 && h2->next)
            {
                h1 = h1->next;
                h2 = h2->next->next;
            }
            h2 = h1->next;
            h1->next = NULL;
            return merge(sortList(head),sortList(h2));
        }
        ListNode *merge(ListNode*h1,ListNode*h2)
        {
            ListNode  *newHead = new ListNode(INT_MIN);
            ListNode  *node =newHead ;
            while(h1 && h2)
            {
                if(h1->val<h2->val)
                {
                    node->next = h1;
                    node = node->next;
                    h1 = h1->next;
                }
                else
                {
                    node->next = h2;
                    node = node->next;
                    h2 = h2->next;
                }
            }
            if(h1)  node->next = h1;
            else    node->next= h2;
            return newHead->next;
        }
    };
    

  • 0
    J

    @potpie O(nlgn) remind me of D&C. exactly same idea.


  • 0
    C

    Following are my non-recursive solution in Java, and it won't use log(n) space complexity. Although I write the iterative solution, I still think it's better to implement it in a recursive way. It's more readable and clear.

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode sortList(ListNode head) {
            int len = 0;
            ListNode iter = head;
            while (iter != null) {
                len++;
                iter = iter.next;
            }
            ListNode fakeHead = null;
            // step represent how long the two merging list is
            for (int step = 1; step < len; step *= 2) {
                fakeHead = new ListNode(0);
                iter = fakeHead;
                fakeHead.next = head;
                ListNode p1 = head;
                ListNode p2 = head;
                for (int i = 0; i < step && p2 != null; i++) {
                    p2 = p2.next;
                }
                while (p2 != null) {
                    iter = merge(iter, p1, p2, step);
                    p1 = iter.next;
                    p2 = iter.next;
                    for (int i = 0; i < step && p2 != null; i++) {
                        p2 = p2.next;
                    }
                }
                head = fakeHead.next;
            }
            return head;
        }
        // merge two listnode with max length len after head
        private ListNode merge(ListNode head, ListNode node1, ListNode node2, int len) {
            int count1 = 0;
            int count2 = 0;
            while (count1 < len || count2 < len) {
                if (count1 < len && (count2 >= len || node2 == null || node1.val <= node2.val)) {
                    head.next = node1;
                    node1 = node1.next;
                    count1++;
                } else {
                    if (node2 == null) break;
                    head.next = node2;
                    node2 = node2.next;
                    count2++;
                }
                head = head.next;
            }
            head.next = node2;
            return head;
        }
    }
    

Log in to reply
 

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