Runtime error in my code, can anyone help?


  • 0
    M

    following is my code along with the thought i have used. can anybody help me solve out why am i getting a run time error in the code.

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            /* 1. count the number of nodes in each list.
            2. find the difference d.
            3. traverse d nodes from the longer list.
            4. compare the address of the next nodes of the current.
            4.1. If same, return next.
            4.2. If not, increment the current of both the list.
            5. return null if no intersection point is found.
            */
            int count1 = 0, count2 = 0;
            ListNode *head1 = headA, *head2 = headB;
            if(head1 == NULL || head2 == NULL)
                return NULL;
            while(head1 != NULL)
            {
                count1++;
                head2 = head2->next;
            }
            while(head2 != NULL)
            {
                count2++;
                head2 = head2->next;
            }
            head1 = headA;
            head2 = headB;
            int d = abs(count1 - count2);
            if(count1 > count2)
            {
                for(int i = 0; i<d; i++)
                    head1 = head1->next;
            }
            else
            {
                for(int i = 0; i<d; i++)
                    head2 = head2->next;
            }
            while(head1 != NULL || head2 != NULL)
            {
                if(head1 == head2)
                    return head1;
                else
                {
                    head1 = head1->next;
                    head2 = head2->next;
                }
            }
            return NULL;
        }
    };

  • 0
    M

    a small typo, thats it. lol! it embarrassing. anyways, you can still offer suggestions to improve it.


  • 0
    S

    First thing I notice is most likely a typo in the following block

    while(head1 != NULL)
    {
        count1++;
        head2 = head2->next;
    }
    

    there should not be any head2


  • 0
    M

    yes, exactly! that was the mistake i had made, which i realized right after submitting the question. anyways, thank you for the help. do you have any suggestions on how this code could be made more efficient?


  • 0
    S

    Here are some of the thoughts. 1) if you can somehow save the tail elements (you are traversing the lists anyway while counting the nodes) then you can just compare the tail nodes and if they don't match you can abort sooner than later. This is because if the tails don't match then the lists are not merging at all so no point running any further code. 2) If the lists are of same length and they are actually merging then traversing the entire length to count and then come back again is extra work. This is because if you can somehow compare the nodes while traversing and if at any point they happen to be same then we already found a merge point so no need to do any further processing.


  • 0
    M

    your first thought is nice. it makes the code more efficient. but i dont understand how to implement the second one. we go through the entire list to find out there lengths. what you are suggesting is that we already know that the lists are of the same length. only in that case we can compare each node while traversing. but to know whether or not they are of the same length, we will need to traverse them atleast once.


  • 0
    S

    You don't necessarily have to know the length to check equality. You can keep on checking equality while doing the traversal, but it might be tricky with the current code you have (two separate loops for counting nodes) if you can combine the counting into a single loop then it's possible. Doing all that may increase the complexity. So I guess you have to think through how to use that thought. :)


Log in to reply
 

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