I think the complexity of my method is O(NlogN), why still gets a TLE?


  • 0
    E

    My method is similar to quicksort, and its space complexity is not strictly const. But I think the time complexity is O(nlogn), why still gets a TLE?

    class Solution {
    public:
        ListNode *sortList(ListNode *head) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if (head == NULL || head->next == NULL)
                return head;
            
            pair<ListNode*, ListNode*> ret = partition(head, NULL);
            return ret.first;
        }
        
        pair<ListNode*, ListNode*> partition(ListNode *begin, ListNode *end) {
            // return the first and last point of the sorted range [begin, end)
            if (begin == NULL || begin->next == end)
                return make_pair(begin, begin);
                
            ListNode *p1 = new ListNode(0);
            ListNode *first_part = p1;
            ListNode *p2 = new ListNode(0);
            ListNode *second_part = p2;
            int base_val = begin->val;
            ListNode *cur = begin->next;
            // partition: first_part is the element less than base_val, second_part is the other
            while (cur != end) {
                if (cur->val < base_val) {
                    first_part->next = cur;
                    first_part = cur;
                } else {
                    second_part->next = cur;
                    second_part = cur;
                }
                cur = cur->next;
            }
            first_part->next = NULL;
            second_part->next = NULL;
            
            pair<ListNode*, ListNode*> first_pair = partition(p1->next, NULL);
            pair<ListNode*, ListNode*> second_pair = partition(p2->next, NULL);
            delete p1;
            delete p2;
            ListNode *new_head = first_pair.first;
            // concatenate
            if (new_head == NULL) {
                new_head = begin;
            } else {
                first_pair.second->next = begin;
            }
            begin->next = second_pair.first;
            if (second_pair.second != NULL)
                return make_pair(new_head, second_pair.second);
            else
                return make_pair(new_head, begin);
            
        }
    };

  • 0
    S

    Could you please explain your algorithm in some word and add comments in your code? It will help others provide right answer easily.


  • 4
    P

    A simple Quicksort has worst case runtime O(N^2) when you don't carefully choose your pivot.

    The following partition would do the trick (but it won't improve the worst case)

        while (cur != end) {
            if (cur->val < base_val || cur->val == base_val && rand() % 2) {
                first_part->next = cur;
                first_part = cur;
            } else {
                second_part->next = cur;
                second_part = cur;
            }
            cur = cur->next;
        }
    

    And I agree that this solution does not meet the constant space requirement because you are using recursion.


  • 0
    E

    Thanks a lot! Now I know what's wrong with my solution.I will try to sovle it using merge sort.


  • 0
    P

    Try to use a merge sort without recursion =)


  • 0
    B

    I have an idea, but I need to disconnect the nodes in the original linked list and keep them(the references) in a queue. And try to use the bottom up merge sort the sort the linked list like you said. But it's time limit exceeded. Could you have a look at my code, I'm appreciated for your help.

    public class Solution {
    
        public ListNode sortList(ListNode head) {
            ArrayList<ListNode> Q = new ArrayList<ListNode>();
            
            if (head == null || head.next == null) return head;
            
            while (head != null) {
                ListNode temp = head.next;
                head.next = null;
                Q.add(head);
                head = temp;
            }
    
            while (Q.size()>1) {
                ListNode a = Q.remove(0);
                ListNode b = Q.remove(0);
                ListNode t = combineLists(a, b);
                Q.add(t);
            }
            return (Q.remove(0));
        }
        
        public ListNode combineLists(ListNode l1, ListNode l2) {
            ListNode head;
            ListNode end;
            
            if (l1 == null) return l2;
            else if (l2 == null) return l1;
            
            if (l1.val<l2.val) {
                head = l1;
                end = l1;
                l1 = l1.next;
            } else {
                head = l2;
                end = l2;
                l2 = l2.next;
            }
            
            while (l1 != null && l2 != null) {
                if (l1.val<l2.val) {
                    end.next = l1;
                    end = l1;
                    l1 = l1.next;
                } else {
                    end.next = l2;
                    end = l2;
                    l2 = l2.next;
                }
            }
            if (l1 == null) {
                end.next = l2;
            } else if (l2 == null) {
                end.next = l1;
            }
            return head;
        }  
    }
    

  • 0
    P

    @baisheng, when you want a queue, don't use ArrayList, you should use LinkedList. See http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist


  • 0
    B

    It's very helpful, and it works! Thank you so much!


  • 0
    K

    I got the same problem. Why quick sort won't do, that's stupid.


  • 0
    J

    My way is below:

    1. divide list two parts L1 and L2
    2. sort L1 and L2 recursively
    3. merge L1 and L2
      ListNode* sortList(ListNode*  head){
       if(!head || !head->next)return head;
      ListNoide* l1,*l2;
      divide(head,l1,l2);
      l1 = sortList(l1);
      l2 = sortList(l2);
      return merge(l1,l2);
    }
    

  • 0
    W
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    M

    Bottom-up merge should be more efficient, but I still got TLE when I wrote in Java, any comments?

    // merge sort by bottom-up

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        LinkedList<ListNode> queue = new LinkedList<ListNode>();
        while (head != null) {
            ListNode next = head.next;
            head.next = null;
            queue.add(head);
            head = next;
        }
        
        while (queue.size() > 1) {
            ListNode a = queue.get(0);
            ListNode b = queue.get(0);
            ListNode c = merge(a, b);
            queue.add(c);
        }
        
        return queue.get(0);
    }
    
    ListNode merge(ListNode a, ListNode b) {
        ListNode head = null;
        ListNode p = null;
    
        if (a.val < b.val) {
            head = a;
            p = a;
            a = a.next;
        }
        else {
            head = b;
            p = b;
            b = b.next;
        }        
        
        while (a != null && b != null) {
            if (a.val < b.val) {
                p.next = a;
                p = p.next;
                a = a.next;
            }
            else {
                p.next = b;
                p = p.next;
                b = b.next;
            }
        }
        
        if (a != null) {
            p.next = a;
        }
        else if (b != null) {
            p.next = b;
        }
        
        return head;
    }
    

  • 0

    The time complexity of quick sort will degrade to O(n^2) in bad cases. I got TLE and then optimized my code a little further for cases where there are lots of duplicates. The code was accepted.

    MAIN IDEA:

    1. Node[start_prev->next] is chosen as sentinel, i.e. node[mid].

    2. Nodes whose data are smaller than sentinel are append to start_prev.

    3. Nodes whose data are equal to sentinal are append to midTail.

    4. Other nodes are kept in place.

      Sadly, my code doesn't meet the requirement "constant extra space" because it have to use a stack, no matter recursive or iterative.

      Also, it will be still slow in the bad cases where the list are already sorted.

      Maybe a function isSorted should be added to preclude these cases, but I doubt if it's worth it.
      Looking forward for some suggestions.

      BYW, I recommend LeetCode to add test cases where the list is already sorted and is holy long. After that I'll have to optimize my code again.

      class Solution {
      public:
      void sort(ListNode start_prev, ListNode end){
      if(start_prev->next == end) return;
      ListNode *mid, *midTail;
      mid = midTail = start_prev->next;
      ListNode *prev = mid, *cur = prev->next;
      while(cur != end){
      if(cur->val < mid->val){
      prev->next = cur->next;
      cur->next = start_prev->next;
      start_prev->next = cur;
      }else if(cur->val == mid->val && prev != midTail){
      prev->next = cur->next;
      cur->next = midTail->next;
      midTail->next = cur;
      midTail = cur;
      }else{
      prev = cur;
      }
      cur = prev->next;
      }
      sort(start_prev, mid);
      sort(midTail, end);
      }

      ListNode *sortList(ListNode *head) {
      	ListNode fake_head(0);
      	fake_head.next = head;
      	sort(&fake_head, NULL);
      	return fake_head.next;
      }
      

      };


Log in to reply
 

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