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

The title

Interview question 02.07. Linked lists intersect

Switch to English to receive dynamic feedback

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:

  • 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: Can you design a solution with O(n) time complexity and only O(1) memory?

Train of thought

  1. This seems like a long problem, but the design summary is to determine whether two lists have elements in common;
  2. We can useMapRecord every element in list A, and then walk through list B to see if the element is inMapThere have been.

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) {
    if(! headA || ! headB) {return null;
    }

    let map = new Map(a);while (headA) {
        map.set(headA);
        headA = headA.next;
    }

    while (headB) {
        if (map.has(headB)) {
            return headB;
        }
        headB = headB.next;
    }

    return null;
};
Copy the code

To optimize the

  1. They’re saying that we’re going to use extra space O(1), so we’re going to have to give up using Map;

  2. The currentA pointer starts from A and runs through A to B.

  3. Let currentB start from B and run through B to A;

    There are three possible outcomes:

So this is the first case, where the intersection happens to be right in the middle, so our third element can meet and go straight back to the node;

In the second case, currentA runs A + B + C after completing A list and then going through SEGMENT B to reach C1, while currentB runs B + C + A after completing B list and then going through segment A to reach C1. We can see that if there are intersections, So when you run through the second list they’re going to meet each other;

So this is the third case where they have no focus, so the time it takes to run both lists is the same. Both of them are always equal to null.

Optimize the code

/** * 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) {
    if(! headA || ! headB) {return null;
    }

    let currentA = headA;
    let currentB = headB;

    while(currentA ! == currentB) { currentA = currentA ? currentA.next : headB; currentB = currentB ? currentB.next : headA; }return currentA;
};
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.