Time out on Leetcode 160 Intersection of Two Linked Lists-CodePudding

I am trying to solve

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

I wanted to use the two pointers to solve it, but the Leet Code site gives me a Time Limit Exceeded error.

My code is shown below:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *tempA = headA, *tempB = headB;
    while (tempA != tempB) {
        if (tempA->next != NULL) { tempA = tempA->next;}
        else { tempA->next = headB;}
        if (tempB->next != NULL) { tempB = tempB->next;}
        else { tempB->next = headA; }
    }
    return tempA;
}

I then tried this existing solution and it works, but I cannot tell what's different:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *tempA = headA, *tempB = headB;
    while (tempA != tempB) {
        if (tempA != NULL) { tempA = tempA->next;}
        else { tempA = headB;}
        if (tempB != NULL) { tempB = tempB->next;}
        else { tempB = headA;}
    }
    return tempA;
}

CodePudding user response：

The algorithm should be a "read-only" algorithm, i.e. there should be no reason to modify the linked lists to determine the solution.

Yet, that is what the first version of the code does: it assigns a new reference to a node's next property. This should never happen: there is no good reason why a node's next property would need to get a new value when the only thing you want to do is "calculate" where a certain node is located and return it.

In this particular case tempA->next = headB; is linking the end of linked list A with the start of linked list B. To picture this, let's imagine the two lists are initially like this:

                              tempA
                               ↓
                             ┌────────────┐
                    headA:─► │ data: 2    │
                             │ next: ───────┐
                             └────────────┘ │    ┌────────────┐
                                            └──► │ data: 3    │
                                            ┌──► │ next: NULL │
         ┌────────────┐      ┌────────────┐ │    └────────────┘     
headB:─► │ data: 4    │      │ data: 5    │ │
         │ next: ──────────► │ next: ───────┘
         └────────────┘      └────────────┘     
           ↑
          tempB

The loop will in the first iterations always execute the if cases, and so after one iteration tempA and tempB will reference the next nodes:

                             ┌────────────┐
                    headA:─► │ data: 2    │          tempA
                             │ next: ───────┐         ↓
                             └────────────┘ │    ┌────────────┐
                                            └──► │ data: 3    │
                                            ┌──► │ next: NULL │
         ┌────────────┐      ┌────────────┐ │    └────────────┘     
headB:─► │ data: 4    │      │ data: 5    │ │
         │ next: ──────────► │ next: ───────┘
         └────────────┘      └────────────┘     
                               ↑
                              tempB

And now, in the second iteration, the first else block will execute tempA->next = headB; which alters that tail node's next property, bringing about the following situation:

                             ┌────────────┐
                    headA:─► │ data: 2    │          tempA
                             │ next: ───────┐         ↓
                             └────────────┘ │    ┌────────────┐
                                            └──► │ data: 3    │
                                            ┌──► │ next: ────────┐
         ┌────────────┐      ┌────────────┐ │    └────────────┘  │  
headB:─► │ data: 4    │      │ data: 5    │ │                    │
     ┌─► │ next: ──────────► │ next: ───────┘                    │
     │   └────────────┘      └────────────┘                      │
     └───────────────────────────────────────────────────────────┘
                               ↑
                              tempB

This is introducing a cycle in the linked list: there is now no more tail node -- there is no node anymore whose next property is NULL. As you can see that means the while condition will from now on always be true,... this has become an infinite loop. This explains why the platform that runs this code is signaling a "time limit exceeded" error.