Nuggets team number online, help you Offer impromptu! Click on theCheck the details

1. Title Description

Enter two linked lists to find their first common node.

Here are two linked lists:

The intersection begins at node C1.

Example 1:

The input

IntersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3Copy the code

The output

Reference of the node with value = 8
Copy the code

Input explanation: The value of the intersection node is 8 (note that it cannot be 0 if two lists intersect). Starting from their respective table headers, linked list A is [4,1,8,4,5] and linked list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersecting node; In B, there are three nodes before the intersection node.

Example 2:

The input

IntersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1Copy the code

The output

Reference of the node with value = 2
Copy the code

Input explanation: The value of the intersection node is 2 (note that it cannot be 0 if two lists intersect). Starting from their respective table headers, linked list A is [0,9,1,2,4] and linked list B is [3,2,4]. In A, there are three nodes before the intersecting node; In B, there is 1 node before the intersecting node.

Example 3:

The input

IntersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2Copy the code

Output:

null
Copy the code

Input explanation: from the respective table headers, linked list A is [2,6,4] and linked list B is [1,5]. Because the two linked lists do not intersect, intersectVal must be 0, and skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so null is returned.

Note:

If two lists do not intersect, null is returned. After the result is returned, both lists must remain in their original structure. It can be assumed that there are no loops in the entire list structure.

Second, train of thought analysis

My train of thought

First of all: how to judge intersection? The most brutal: 2 linked lists all go to the end to see them a different. How to get the first intersection:

  1. Calculate the length of two linked lists, and then the long one goes through the difference part first, and then they go together to determine whether they are equal. If they are equal, the first intersection point is O(3n).
  2. With the help of stack, put two linked lists into the stack, and keep popping, when different, the previous popup is the first intersection point (space complexity is high).
  3. How do I do recursion?

The best way of thinking

  • The use of double Pointers, romantic encounter, which contains the idea of mathematics:
    • If a is equal to B at the beginning, then we’re going to meet each other in a, which is the best case.
    • If a! If it’s equal to b, then A goes A plus b plus L and b goes b plus A plus L
    • In short, the reason these moves must meet is a simple mathematical formula: A +L+b= B +L+a => A +b+L= B +a+L
  • For example
    • The length of the two roads is A: A +L+ B and B: B +L+ A. The length of A and the length of B respectively means that you can only walk in A section, you can ride A bicycle in B section, and you can only take A bus in L section.
    • Q: If two people start at the same time, one on road A and the other on road B, will they reach the finish line at the same time?
      • That is, the lengths of A and B are actually the same, consisting of A chain and B chain, but in different order, but it must take the same number of steps to complete the chain.

AC code

My implementation is too ugly, so it won’t stick out. Here’s the best way to write it:

public ListNode getIntersectionNodeBetter(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode n1 = headA;
    ListNode n2 = headB;
    while(n1 ! = n2) {// Walk your own way to take another's road, until we meet
      	// If null == null, return true.
        n1 = n1 == null ? headB : n1.next;
        n2 = n2 == null ? headA : n2.next;
    }
    return n1;
}
Copy the code

Four,

A lot of people put this solution is very romantic 😆, but this solution is actually more routine, not really want to. But this is a very classical solution, and I think I can figure it out.