Why still TLE{1,1}?


  • 0
    R

    It is the first time I used insertion sort to sort linked list.
    I have consulted some of the discussions, but my code still ran into time limit exceeded {1,1}. I tried to make sure that there is no infinite loop, but it seems there still is. Can anybody tell me how did it happen?

    public class Solution {
    public ListNode insertionSortList(ListNode head) {
    if(head==null || head.next==null){
    return head;
    } else{
    ListNode neoHead = new ListNode(head.val);
    ListNode neoNode = neoHead;
    ListNode pointer = head.next;

            while(pointer!=null){
                if (pointer.val<=neoHead.val){
                    ListNode oldHead = neoHead;
                    neoHead = pointer;
                    neoHead.next = oldHead;
                } else {
                    if (neoNode!=null && neoNode.next==null && pointer.val>neoNode.val){
                        ListNode tail = new ListNode(pointer.val);
                        neoNode.next = tail;
                    }
                    while (neoNode.next!=null){
                        if (pointer.val>neoNode.val && pointer.val<=neoNode.next.val){
                            ListNode temp1 = new ListNode(pointer.val);
                            ListNode temp2 = neoNode.next;
                            neoNode.next = temp1;
                            temp1.next = temp2;
                        }
                        neoNode = neoNode.next;
                    }
                }
                pointer = pointer.next;
            }
            return neoHead;
        }
    }
    

    }


  • 0
    M

    Since the first and second values are identical, you keep entering the conditional in the while loop, which ends up lengthening the list by 1 node each iteration. Since it never decreases the length, nor advances through the list, the while loop will never have pointer be null. The algorithm therefore has an infinite loop, leading to the TLE.

    As you add pointer.next being equal to the sorted list, when you use pointer=pointer.next;, you start traversing the sorted list, which grows as you keep adding pointer to the start. Instead, keep track of the remainder as soon as you start the loop(ListNode remainder = pointer.next;) and use that to advance pointer at the end(pointer = remainder;) instead of pointer=pointer.next;.

    If you do not care for the effort of changing your code, here it is with the changes already made.

    public ListNode insertionSortListD(ListNode head) { 
        if(head==null || head.next==null){ return head; } 
        else{ 
            ListNode neoHead = new ListNode(head.val);
            ListNode neoNode = neoHead;
            ListNode pointer = head.next;
            while(pointer!=null){
                ListNode remainder = pointer.next;
                if (pointer.val<=neoHead.val){
                    ListNode oldHead = neoHead;
                    neoHead = pointer;
                    neoHead.next = oldHead;
                } else {
                    if (neoNode!=null && neoNode.next==null && pointer.val>neoNode.val){
                        ListNode tail = new ListNode(pointer.val);
                        neoNode.next = tail;
                    }
                    while (neoNode.next!=null){
                        if (pointer.val>neoNode.val && pointer.val<=neoNode.next.val){
                            ListNode temp1 = new ListNode(pointer.val);
                            ListNode temp2 = neoNode.next;
                            neoNode.next = temp1;
                            temp1.next = temp2;
                        }
                        neoNode = neoNode.next;
                    }
                }
                pointer = remainder;
            }
            return neoHead;
        }
    }
    

    As a side note, though it's not the case here, TLE also happens when your algorithm works, but takes longer than the ideal algorithm (as defined by leetcode). This algorithm does have an infinite loop, but TLE does not necessarily mean there is one.


  • 0
    R

    Thank you! Your suggestion worked and with some digging I remembered why keeping track of the remainder is important. Thanks again! :)


Log in to reply
 

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