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

[B] [C] [D]

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.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 output: Intersected at '8' 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.Copy the code

Example 2: 

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 output: Intersected at '2' 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.Copy the code

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 From their respective 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. The two lists do not intersect, so null is returned.Copy the code

Tip:

  • The number of nodes in listA is M
  • The number of nodes in the listB is N
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • If listA and listB do not intersect, intersectVal is 0
  • If there is an intersection between listA and listB, intersecting intersectVal == listA[skipA + 1] == listB[skipB + 1]

Advanced: Can you design a solution with O(n) time complexity and only O(1) memory?

How many cases are there in A given linked list A and B?

As shown in the figure above, according to the meaning of the question, we can sum up a total of 6 possible situations, so we can deal with these 6 situations respectively through the code.

Here is the code implementation:

Var getIntersectionNode = function (headA headB) {/ / a single linked list is empty if (headA = = = null | | headB = = = null) return null; If (headA === headB) return headA; // Iterate over linked list A and mark let cur = headA; While (cur){if(cur.next === headB) return headB; cur.tag = 'A' cur = cur.next; } // iterated list B cur = headB; while(cur && ! Cur. tag){if(cur.next === headA) return headA; cur = cur.next; } // The first intersection node or null return cur; };Copy the code

At this point, we are done with Leetcode – Interview question 02.07- linked list intersection

If you have any questions or suggestions, please leave a comment!