Why this solution is time limited


  • 0
    S
    public ListNode partition(ListNode head, int x) {
        ListNode result=new ListNode(-1);
        ListNode resultpoint=result;
        ListNode headpoint=new ListNode(-1);
        headpoint.next=head;
        while(headpoint.next!=null){
            if(headpoint.next.val<x)
            {
                resultpoint.next=headpoint.next;
                resultpoint=resultpoint.next;
                headpoint.next=headpoint.next.next;                
            }
            else{
                headpoint=headpoint.next;
            }
        }
        resultpoint.next=head;
        return result.next;
    }
    

    the code result is time-limit-exceeded .
    i run the code on my computer eclipse and input the data as the test case [{1},2] show.
    i debug and find on my eclipse ,the code run well and excalty.
    can some body tell me the resaon?


  • 0
    C
    public ListNode partition(ListNode head, int x) {
        if (head==null) return null;
        ListNode lastSmall = null;
        ListNode firstBig = null;
        ListNode lastBig = null;
        ListNode index = head;
        while(index!=null) {
            if (index.val<x) {
                if (lastSmall==null){
                    lastSmall = index;
                }
                else {
                    lastSmall.next = index;
                    
                }
            }
            else {
                if (firstBig==null){
                    firstBig = index;
                    lastBig = firstBig;
                }
                else {
                    lastBig.next = index;
                    lastBig = index;
                }
            }
            index = index.next;
        }
        if (lastSmall!=null && firstBig!=null)
        lastSmall.next = firstBig;
        return head;
    }
    

    I have the same problem. I think it's O(1), but got time-limit when the case was {(2,1), 2}


  • 0
    K

    Same problem.


  • 0
    K

    Check this answer by wind.memory.cn:

    "I finally figured out why my code exceed the time limit. I didn't write the code to deal with the last node's next pointer, so the pointer points to the head, and the link list become a loop. The time limit exceed happened during the test case. So I couldn't find the reason that my code exceed the time limit."

    answered Dec 23, 2014 by wind.memory.cn (320 points)


Log in to reply
 

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