“This is the 26th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

Topic describes

Given the head nodes of two singly linked lists, headA and headB, find and return the start node where the two singly linked lists intersect. If two linked lists do not intersect, null is returned.

The two linked lists intersect at node C1:

The problem data guarantees that there are no rings in the chain.

Note that after the function returns the result, the list must retain its original structure.

Thought analysis

It’s very difficult to find the intersecting nodes from the front to the back, except in n^2 time. But all the nodes that intersect are the same, so we can think about if we look backwards, we can find the nodes that intersect.

  • Go back to front and declare two stacks, iterating over and over to write elements to the stack
  • Keep popping the elements on the stack until the nodes on stack 1 and 2 are different, and find the last node that was popped.

The main code is as follows:

 while(! (stk1.empty() || stk2.empty())){
    ListNode* idx1 = stk1.top(a); stk1.pop(a); ListNode* idx2 = stk2.top(a); stk2.pop(a);if(idx1 -> val ! = idx2 -> val){if(pre == nullptr)return nullptr;
        cout << pre ->val << endl;
        return pre;
    }
    pre = idx1;
}
Copy the code

However, this method can not overcome the force buckle.

If two points intersect, we can divide A into Apre and Common, and divide B into Bpre and common. We set headA and headB as the starting point respectively, and we just need to let both sides walk through


A p r e + B p r e + c o m m o n Apre + Bpre + common

The length of, can let the two meet.

The specific implementation

 while(tmpA ! = tmpB) { tmpA = tmpA->next; tmpB = tmpB->next;if(tmpA == nullptr){
                tmpA = headB;
            }
            if(tmpB == nullptr){ tmpB = headA; }}Copy the code

Core code as above

conclusion

The first method is O(n) in time, but also O(n) in space. While the second time complexity is constant, the space complexity is indeed O(1). Greatly saving space consumption.