Intersection of two single linked list, why TLE?


  • 0
    L

    I used the method of "Make circle in first list, and iterates the second to find if it has circle." But my method turns out to be "Memory Limit Exceed." I do not understand why, since I only use three pointers which may occupy 8or4 *3 bytes, why will this results in memory limit exceed?

    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if(headA==NULL||headB==NULL)
                return NULL;
            ListNode* tailA=headA;
            while(tailA->next!=NULL)
            {
                tailA = tailA->next;
            }
            tailA->next = headA;
            ListNode* fast=headB;
            ListNode* slow=headB;
            while(fast&&fast->next)
            {
                fast = fast->next->next;
                slow = slow->next;
                if(fast==slow)
                {
                    fast = headB;
                    while(fast!=slow)
                    {
                        fast = fast->next;
                        slow = slow->next;
                    }
                    tailA->next = NULL;
                    return fast;
                }
            }
            return NULL;
        }
    };

  • 0
    S

    Please see the following post which has the same problem as yours:

    https://oj.leetcode.com/discuss/18173/my-c-code-using-cycle-list-but-mle


  • 0
    L

    thank you very much!


Log in to reply
 

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