Write a program to find the start node where two singly linked lists intersect.

Here are two linked lists:

The intersection begins at node C1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Reference of the node with value = 8 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 Reference of the node with value = 2 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 output: null 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. Explanation: The two lists do not intersect, so null is returned.Copy the code

Their thinking

  • Create two Pointers 和 , respectively initialized to a linked listA 和 BThe header of the. And then let them go back node by node.
  • whenWhen you reach the end of the list, relocate it to the listB(you read that right, linked list B); Similarly, whenWhen the end of the list is reached, relocate it to the head of list A.
  • If at some point 和 Meet,/Is the intersection node.
  • To see why this works, consider the following two linked lists: A={1,3,5,7,9,11} and B={2,4,9,11}, intersecting at node 9. Because b.length (=4) < A.Length (=6), 比 22 fewer nodes, you get to the tail first. willRedirect to the head of A,After redirecting to the head of B,thanI’m going to go 2 more nodes. So, they both get to the intersection at the same time.
  • If two lists intersect, they must end with the same node. So when/When you reach the end of the list, record the listA/BThe corresponding element. If the final element is different, the two lists do not intersect.

Code implementation

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */
var getIntersectionNode = function(headA, headB) {
    let p1 = headA
    let p2 = headB
    while(p1 ! = p2){ p1 = p1 ? p1.next : headB p2 = p2 ? p2.next : headA }return p1 ? p1 : p2 
};
Copy the code

performance

Time complexity:

Space complexity: