Why TLE even given input {2,1}, 2


  • 0
    J
    class Solution {
    public:
       ListNode *partition(ListNode *head, int x) {
            ListNode *p=head;
            ListNode *less = new ListNode(0);
            ListNode *pLess = less;
            ListNode *greater= new ListNode(0);
            ListNode *pGreater= greater;
            while (p!=NULL){
                if (p->val>=x){
                    pGreater->next=p;
                    pGreater=p;
                } else {
                    pLess->next=p;
                    pLess=p;
                }
                if (p->next==NULL)break;
                p=p->next;
            }
            pLess->next=greater->next;
            head=less->next;
            return head;
        }
    };
    

    My ideal is maintaining two lists, one for greater nodes, and one for less nodes. And concatenate them together.
    Its time complexity is O(N). And I am sure there is no infinite loop, because I run the test cases on my computer and it works well. I don't know what is going on, here.


  • 9
    M

    I actually ran into this same error on my solution. What is happening is that the tester is running in a infinite loop trying to find null in the linked list to end.

    The node 2 is taken and placed into the greater list, but its next value is still pointing at node 1. Node 1 is then placed into the lesser list, and its next is assigned to the start of the greater list, node 2, after the while loop ends. At this point, 1.next = 2 and 2.next = 1. You return this circular list, and the tester runs through it trying to evaluate the list as correct or not. It never reaches null, so it gets stuck in an infinite loop outside of Solution until your time runs out.

    To fix this, break the tie between the greater list and the lesser list.


  • 0
    J

    Thank you so much! You are right. I get accepted by setting the end of the list to NULL.


  • 0
    E

    hi, jiezhou, after looking your code, there are two problem; first, if (p->next == NULL) .., i think it`s unnecessary, because it will end the loop automaticly. second, you have to add NULL to the end of greater, you can pass case in your computer because your IDE is smart. orz


Log in to reply
 

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