Why this result in time limit exceed?


  • 0
    L

    Please see the code below and help. Thanks a lot TT

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • struct ListNode *next;
      
    • };
      /
      struct ListNode
      mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {

      if(l1 == NULL)
      return l2;
      else if(l2 == NULL)
      return l1;

      struct ListNode* myHead;
      struct ListNode* tmp = NULL;
      struct ListNode* p2;

      if(l1->val <= l2->val)
      {
      myHead->next = l1;
      p2 = l2;
      }
      else
      {
      myHead->next = l2;
      p2 = l1;

      }
      struct ListNode* p1 = myHead;

      while((p1->next!=NULL) && (p2!=NULL))
      {
      if(p2 -> val <= p1->next ->val)
      {
      tmp = p2->next;
      p2->next = p1 -> next;
      p1->next=p2;
      p2=tmp;
      }
      p1=p1->next;
      }
      return myHead->next;
      }


  • 0
    M

    There are a lot of problems in your code, so the TLE problem is because you didn't understand the head node and the head pointer. The edited code are(containing bugs):

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
        if(l1 == NULL)
            return l2;
        else if(l2 == NULL)
            return l1;
        
        struct ListNode* myHead;
        struct ListNode* tmp = NULL;
        struct ListNode* p2;
        
        if(l1->val <= l2->val)
        {
            myHead = l1; // myHead isn't a head node, but a pointer
            p2 = l2;
        }
        else
        {
            myHead = l2;  // myHead isn't a head node, but a pointer
            p2 = l1;
        
        }
        struct ListNode* p1 = myHead;
        
        while(p2!=NULL) // p1 never be NULL
        {
            if(p1->val <= p2->val) // myHead isn't a head node, but a pointer
            {
                tmp = p2->next;
                p2->next = p1->next;
                p1->next=p2;
                p1 = p2; // prepare for next loop
                p2=tmp;
            }
            p1=p1->next;
        }
        return myHead; // myHead isn't a head node, but a pointer
    }
    

    But if you run the code you will meet a lot of problem:
    such as:

    Input:
    0
    1->2->3
    The next status is:
    0->1->NULL
    2->3
    

    So, there will be an access to (NULL)->next, RTE. It's easy to patch the code:

    ... ...
        while(p2!=NULL)
        {
            if(p1->val <= p2->val)
            {
                tmp = p2->next;
                if(p1->next == NULL) { // PATCH
                    p1->next = p2;
                    break;
                }
                p2->next = p1->next;
                p1->next=p2;
                p1 = p2;
                p2=tmp;
            }
            p1=p1->next;
        }
        return myHead;
    ... ...
    

    But there is still a bug:
    such as:

    Input:
    1->9
    7->8
    The next status is:
    1->7->9
    8
    

    Obvious WRONG. So please try to solve the bug yourself? May be new potential bugs?


  • 0
    L

    thank you so much, I've solved the problem~


Log in to reply
 

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