Memory Limit Exceeded But I almost didn't allocate any new memory.


  • 0
    S

    Here is my code. The idea is there are 3 length in the intersected list:

    • x - the length in the list started with headA before the intersect point
    • y - the length after the intersect point
    • z - the length in the list started with headB before the intersect point

    By iterating from headA we can get:
    x + y = m

    By iterating from headB we can get:
    z + y = n

    Reverse list started with headB and iterate from headA we can get:
    x + z = q

    We can easily solve this equation:
    x = (m - n + q) / 2

    And finally we can get the intersect node.

    However it's Memory Limit Exceeded. I don't understand why.

    class Solution {
    public:
        int getLen(ListNode * head) {
            int len = 0;
            ListNode * cur = head;
            while (cur != NULL) {
                cur = cur->next;
                len++;
            }
            return len;
        }
    
        ListNode * reverse(ListNode * head) {
            if (head == NULL || head->next == NULL) return head;
            ListNode * prev = head;
            ListNode * cur = head->next;
            while (cur != NULL) {
                ListNode * next = cur->next;
                cur->next = prev;
                prev = cur;
                cur = next;
            }
            head->next = NULL;
            return prev;
        }
    
        ListNode * getTail(ListNode * head) {
            if (head == NULL || head->next == NULL) return head;
            ListNode * prev = head;
            ListNode * cur = head->next;
            while (cur != NULL) {
                prev = cur;
                cur = cur->next;
            }
            return prev;
        }
    
        // if n is 0, return the first node
        ListNode * getNthNode(ListNode * head, int n) {
            ListNode * cur = head;
            while (n > 0) {
                cur = cur->next;
                n--;
            }
            return cur;
        }
    
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if (headA == NULL || headB == NULL) return NULL;
            ListNode * newHeadB = reverse(headB);
            ListNode * tailA = getTail(headA);
            if (tailA != headB) return NULL; // no intersection;
            int q = getLen(headA);
            int n = getLen(newHeadB);
            reverse(newHeadB); // recover the headB
            int m = getLen(headA);
            int x = (m - n + q) / 2;
            return getNthNode(headA, x);
        }
    };

  • 0
    S

    I got it. I forget to recover headB if there is no intersect.


Log in to reply
 

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