“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

List intersection

Title addressClick on the

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 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.

brainstorming

In fact, as soon as I got this problem, the first thing I thought about was, I want to reverse the two lists, and then I want to go through the two lists again to find where the fork starts, which is the point where it intersects. In fact, this idea is feasible, but in this case, they restrict the list to maintain its original structure, so it is abandoned.Copy the code

The theoretical analysis

To understand the solution to this problem, you actually need to understand the following picture, very simple elementary school math problem.

Suppose two people start at A and B respectively and run at the same speed. The one who reaches D starts from the other’s starting point and continues running

Q: Who gets to point C first?

Answer: A runs (A -> C -> D) + (B -> C) + (B -> C), length h + n + m B runs (B -> C -> D) + (A -> C), length M + n + H H plus n plus m. And since they have the same speed, they must reach point C at the same time!!Copy the code

Answer key

So similarly, in this case, we could have done it with two Pointers

Two Pointers, N1 and n2, are created at a1 and B1 respectively. Both Pointers move forward one step at a time. Whoever points to C3 will continue to move from the other starting point until they are equal and then stop. Because of our theoretical analysis of the math problem above, in this case, the two must meet.Copy the code

Code (javascript)

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let PA = headA; let PB = headB; while(PA ! = PB){//A takes A step forward each time, if A reaches the end, then proceed from B to PA = PA === null? HeadB: PA = pa. next //B takes A step forward each time, if B comes to the end, then proceed from A point PB = PB === null? headA : PB = PB.next } return PA };Copy the code