This is the 17th day of my participation in the August More text Challenge. For details, see:August is more challenging

Intersecting Linked List (Question Number 160)

The title

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

In the figure, two linked lists intersect at node C1:

The topic data guarantees that there are no rings in the entire chain structure.

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

Example 1:

Enter intersectVal =8, listA = [4.1.8.4.5], listB = [5.0.1.8.4.5], skipA = 2, skipB = 3Output: Intersected at'8'Explanation: The value of the intersecting node is8(Note that if two lists intersect, it cannot be0). Starting from the header of each list, A is [4.1.8.4.5], the linked list B is [5.0.1.8.4.5]. In A, there is before the intersection node2A node; In B, there is before the intersection node3A node.Copy the code

Example 2:

Enter intersectVal =2, listA = [0.9.1.2.4], listB = [3.2.4], skipA = 3, skipB = 1Output: Intersected at'2'Explanation: The value of the intersecting node is2(Note that if two lists intersect, it cannot be0). Starting from the header of each list, A is [0.9.1.2.4], the linked list B is [3.2.4]. In A, there is before the intersection node3A node; In B, there is before the intersection node1A node.Copy the code

Example 3:

Enter intersectVal =0, listA = [2.6.4], listB = [1.5], skipA = 3, skipB = 2Output:nullExplanation: Starting from the header of each list, A is [2.6.4], the linked list B is [1.5]. Since these two linked lists do not intersect, intersectVal must be0While skipA and skipB can be any value. The two lists do not intersect, so returnnull 。
Copy the code

Tip:

  • listAThe number of nodes ism
  • listBThe number of nodes isn
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • iflistA 和 listBThere’s no intersection,intersectVal 为 0
  • iflistA 和 listBHave a intersection point,intersectVal == listA[skipA + 1] == listB[skipB + 1]

Advanced:

  • Student: Can you design a time complexityO(n)And only inO(1)Memory solution?

link

Leetcode-cn.com/problems/in…

explain

This one. This one is Jane I failed.

Failed again, wood method, can think of double pointer, but can not think of double pointer solution, is the next lost.

The normal solution is easy to think of, first scan the list of A, put the current node in A Set or Map, really lazy to use the object. The reason for using these data types is that the search operation is O(1), so you don’t need to do complex search operations.

It is recommended to use sets because they do not store values, whereas both maps and objects do.

If A node in B appears in the Set, then prove that B and A intersect. Return the current node. If B does not intersect at the end of the list, return null to prove that the two lists do not intersect.

This is a very simple idea, and any normal person can think of it, but the difficulty is the double pointer solution.

You can think of a double pointer, but how do you solve it? Originally wanted to use the fast pointer, the result thought for a long time, write a lot of code, the logic is extremely complex, still did not think of the result.

The positive solution is actually a different form of the speed pointer, but of course it can be interpreted differently.

Imagine two linked lists that look like this:

A: 	 a1 -> a2
                     -> c1 -> c2 -> c3
B: b1 -> b2 -> b3    
Copy the code

A and B intersect at c1, and B is one node longer than A. If I make B go one step further than A at the beginning, will both Pointers point to c1? Is that where the answer comes in?

If both Pointers point to null at the end of the list, then the answer to this question is that the two lists do not intersect.

At this point, there is only one problem to solve — if you determine the difference between the lengths of the two lists, that is, how many nodes one is ahead of the other.

There is a very simple, but also very clever way.

Let A and B start at the same time, so that A goes to the head of B, and B goes to the head of A.

In the previous example, when the pointer A goes to the end of the line, it points to the node B1 on the list OF B, and it hasn’t gone to the end of the line yet, but when the pointer B goes to the end, it points to the node A1 on the list of A, and it has gone to the node B2.

So is pointer A ahead of pointer B in terms of the difference between the two lists? I’m going to go the whole length one more time and I’ll get to the final solution.

Exchange position this wave really did not expect, all of a sudden completed the fast and slow pointer of two positions, a step in place.

In order for the two objects to be equal, they must point to the same memory location. Otherwise, the two objects will not be equal even if they have the same value. Therefore, it is recommended to write the test case as follows:

const COMMON = {"val":8."next": {"val":4."next": {"val":5."next":null}}}
const A = {"val":4."next": {"val":1."next": COMMON}}
const B = {"val":5."next": {"val":6."next": {"val":1."next": COMMON}}}
Copy the code

Both list A and list B refer to the COMMON list, so that the equality judgment can be used when the subsequent loop to the specified location.

Your own answers (Set)

Set is simple 👇 :

var getIntersectionNode = function(headA, headB) {
  const aSet = new Set(a)while (headA) {
    aSet.add(headA.val)
    headA = headA.next
  }
  while (headB) {
    if (aSet.has(headB.val)) return headB
    headB = headB.next
  }
  return null
};
Copy the code

There is nothing to say about this. The idea is the same as in the explanation.

Better method (double pointer)

It looks easier with a double pointer, probably because you don’t have to store to a Set.

var getIntersectionNode = function(headA, headB) {
  if(! headA || ! headB)return null
  let pA = headA
  let pB = headB
  while(pB ! == pA) { pA = pA ? pA.next : headB pB = pB ? pB.next : headA }return pA
};
Copy the code

Just keep updating the positions of pA and pB, and if they’re equal, end the loop.

It doesn’t matter what the current value is, if it’s null, prove that the two lists don’t intersect, just return it, if it’s normal, just return it, so the two lists intersect.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)