Title Description

Give you the header nodes of two single-chain lists, headA and headB. Find out and return the starting node where the two single-chain lists intersect. Returns null if the two linked lists do not intersect.

Diagram showing the intersection of two chains starting at node c1:

Topic data ensures that no loops exist in the entire chain structure.

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

Solving problems

Hash Table Storage

To determine whether two linked lists intersect, a hash set can be used to store the linked list nodes.

The chain headA is first traversed and each node in the chain headA is added to the hash set. Then traverse the chain table headB to determine if the node is in the hash set for each node traversed:

If the current node is not in the hash set, continue traversing the next node;

If the current node is in the hash set, then all subsequent nodes are in the hash set, that is, all nodes from the current node are in the intersection of the two chains, so the first node traversed in the chains headB is the node where the two chains intersect and returns the node.

If all the nodes in the chain table headB are not in the hash set, the two chains do not intersect, returning null.

Double Pointer

Essentially, two pointers, PA and PB, point to head A and headB respectively, moving both pointers forward 1 at a time, PA to the end of the A-chain table, then starting from the headB-chain header, PB to the end of the B-chain table, and then starting from the chain header of head A until the two pointers PA==PB. I feel a little like a playground chase problem in math.

Put a group of pictures of the big guys:

Input and output examples

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'
Explanation: The value of the intersecting node is 8 (note that if two linked lists intersect, they cannot be 0).
Starting with their respective headers, list A is [4,1,8,4,5], and list B is [5,0,1,8,4,5].
In A, there are two nodes before the intersecting nodes. In B, there are three nodes before the intersecting nodes.

Example 2

 

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at'2'
Explanation: The value of the intersecting node is 2 (note that if two linked lists intersect, they cannot be 0).
Starting with their respective headers, list A is [0,9,1,2,4], and list B is [3,2,4].
In A, there are three nodes before the intersecting nodes. In B, there is one node before the intersecting nodes.

Example 3

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Interpretation: Starting from their respective headers, list A is [2,6,4], and list B is [1,5].
Because the two lists do not intersect, intersectVal must be 0, and skipA and skipB can be any value.
The two lists do not intersect, so null is returned.

Code

Hash Table Storage

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> hashset = new HashSet<>();
        ListNode tem = headA;
        while(tem != null){
            hashset.add(tem);
            tem = tem.next;
        }
        tem = headB;
        while(tem != null){
            if(hashset.contains(tem)){
                return tem;
            }
            tem = tem.next;
        }
        return null;
    }
}

Double Pointer

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}