Topic describes

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 linked lists do not intersect, null is returned.

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.

The original title

Hash Map idea

If you have done linked list loop detection before or read the author’s last article on linked list loop detection, you can try not to analyze this topic and try to guess the Map implementation. It is very helpful to strengthen your sense of code language

Subject analysis

  1. Create a Map to store data (all hash ideas do this)
  2. To determine whether two linked lists intersect, we can take a linked list as a benchmark, iterate through the loop and put all the nodes of the list into the Map that has been created.
  3. Iterate the second list again. If the two lists intersect, the first data found in the Map is the value of the intersecting node
  4. There are no duplicate nodes in the Map, return NULL
  5. Boundary value processing: if one of the two linked lists is empty, they do not want to intersect. The two linked lists have only one node and their values are inconsistent, so they do not intersect

Code implementation

var getIntersectionNode = function (headA, headB) {
    if(! headA || ! headB)return null;
    const mapper = new Map(a);let nodeA = headA;
    let nodeB = headB;
    while (nodeA) {
        mapper.set(nodeA, nodeA);
        nodeA = nodeA.next;
    }

    while (nodeB) {
        if (mapper.get(nodeB)) {
            return nodeB;
        }
        nodeB = nodeB.next;
    }

    return null;
};
Copy the code

Two-pointer method

Thought analysis

1. Two linked lists each have two head nodes, each starting from scratch. The proof structure is shown in the following figure

As can be seen from the above figure, whether the linked list intersects or not, a + B + C === B + C + A, the difference between the two is that if the list intersects, the intersecting nodes are equal; if not, there are still no equal nodes after the cycle ends.

Code implementation

var getIntersectionNode = function (headA, headB) {
    if(! headA || ! headB)return null;
    let nodeA = headA;
    let nodeB = headB;

    while(nodeA ! == nodeB) { nodeA = nodeA ===null ? headB : nodeA.next;
        nodeB = nodeB === null ? headA : nodeB.next;
    }

    return nodeA;
};
Copy the code