why TLE ? pls help..o(n) solution


  • 0
    P
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode partition(ListNode head, int x) {
            ListNode bs=null;
            ListNode be=null;    
            ListNode as=null;
            ListNode ae=null;
        
            
            while(head!=null){
                
                if(head.val<x){
                    if(bs==null){
                        bs=head;
                        be=bs;
                    }
                    else
                    {
                        be.next=head;
                        be=head;
                        
                    }
                    
                }
                else {
                    if(as==null){
                        as=head;
                        ae=as;
                    }
                    else
                    {
                        ae.next=head;
                        ae=head;
                        
                    }
                    
                }
                
                head=head.next;
            }
            
            if(bs==null)
              return as;
            be.next=as;
            return bs;
            
        }
    }```
    
    please suggest why this gives me TLE ? It is O(n)

  • 1

    @prasaanth You need to remove the existing Next connections on the original linked list at the end of the iteration.

    Otherwise in some test case, the tail node of latter half list may have Next link to the former half list, which results in an infinite loop when LeetCode trying to check the list you return.


Log in to reply
 

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