TLE error on list partition question


  • 1
    X

    this is my code of list partition. I think this solution is O(n) complexity, but I got TLE error in the test case {1, 2} 2. Please help!

    public class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null||head.next==null) return head;
        ListNode before=null;
        ListNode after=null;
        ListNode h1=null;
        ListNode h2=null;
        while(head!=null){
            ListNode temp=head.next;
            head.next=null;
            if(head.val<x){
                if(before==null){
                    before=head;
                    h1=before;
                }else{
                   before.next=head;
                   before=before.next;
                }
            }else{
                if(after==null){
                    after=head;
                    h2=before;
                }else{
                    after.next=head;
                    after=after.next;
                }
            }
            head=temp;
        }
        
        if(h1==null) return h2;
        
        before.next=h2;
        return h1;
    }
    

    }


  • 0
    S

    It is more likely having an endless loop, which causes by assigning next for before or after in edge case. Please leave comments in code that helps to understand. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    W

    Maybe you forgot to add
    after.next=None

    The end of the returned list should be a blank pointer.


Log in to reply
 

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