LESSON 307 OF 414 · LINKED LISTS

Intersection of Two Linked Lists in Rust: O(m + n) Time, O(1) Space

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return None.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
listA - The first linked list.
listB - The second linked list.
skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return None.

Constraints:

The number of nodes of listA is m.
The number of nodes of listB is n.
1 <= m, n <= 3 * 10⁴
The value of each node is between 1 and 10⁵
0 <= skipA < m
0 <= skipB < n
intersectVal is 0 if listA and listB do not intersect.
intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?

STEP 1 OF 20

Guided

Ctrl + Enter to check

Intersection Of Two Linked Lists in Rust, explained

Problem overview

The function get_intersection_node receives the heads of two singly linked lists, head_a and head_b, and returns the node where they meet, or None when they never do. Two lists intersect when, from some node on, they are the same nodes: they share one common tail. Each list can have a different number of nodes before that point.

In the first example, list A is 4, 1, 8, 4, 5 and list B is 5, 6, 1, 8, 4, 5. The nodes holding 8, 4, 5 are shared, so the answer is the node holding 8. A has two nodes before it and B has three. The two lists must keep their structure, and there are no cycles. The follow-up asks for O(m + n) time and O(1) memory, where m and n are the lengths.

In this lesson a Link is an optional shared pointer to a node: Option<Rc<RefCell<...>>>. Rc lets two lists own the same node, which a plain Box cannot do, and RefCell gives access to the node's fields through borrow().

Approach: align the ends, then walk together

The brute force compares every node of A with every node of B, which costs O(m * n). A hash set of A's nodes brings the time to O(m + n) but uses O(m) memory. The constant-memory idea uses one fact: because the tail is shared, both lists end with the same number of nodes after the meeting point. Only the part before the meeting point can differ in length.

So measure both lists. Suppose A is longer by d nodes. Those d extra leading nodes of A cannot be the intersection, because B has no node that far back to match. Skip them. Now both pointers are the same distance from the end, and walking them forward together makes them reach the shared node on the same step. If there is no shared node, both reach the end together, and the end is None on both sides.

For the first example the lengths are 5 and 6, so B skips its first node and stands on 6. A stands on its head, 4. The pointers differ, so both advance: A is on 1 and B is on its own 1, which is a different node with the same value, so they differ again. They advance once more and both stand on the node 8, the same allocation, so the loop stops and the function returns it.

Step by step

Measure both lists with a helper that is written last: Self::list_len(&head_a) and the same for B.
Clone the heads into the walkers a and b. Cloning an Rc copies the pointer and increases the reference count by one. The nodes are not copied.
Skip A's extra nodes with for _ in 0..len_a.saturating_sub(len_b). When A is not longer, saturating_sub gives 0 and the loop does nothing.
Step forward in two statements. First read the next link into a variable, then assign it to a.
Do the same for B with the arguments of saturating_sub swapped.
Walk together with while !Self::ptr_eq(&a, &b), advancing both walkers on each pass.
Return a. When the loop ends, both walkers are on the intersection node, or both are None.
Write ptr_eq, which compares by identity: two Some links are equal if Rc::ptr_eq says they share the same allocation, two None links are equal, and a mixed pair is not.
Write list_len: a counter, a cloned cursor, and a while let Some(node) = cur loop that increments the counter and moves the cursor to node.borrow().next.clone().

The solution in Rust

impl Solution {
    fn get_intersection_node(head_a: Link, head_b: Link) -> Link {
        let len_a = Self::list_len(&head_a);
        let len_b = Self::list_len(&head_b);
        let mut a = head_a.clone();
        let mut b = head_b.clone();
        for _ in 0..len_a.saturating_sub(len_b) {
            let next = a.as_ref().unwrap().borrow().next.clone();
            a = next;
        }
        for _ in 0..len_b.saturating_sub(len_a) {
            let next = b.as_ref().unwrap().borrow().next.clone();
            b = next;
        }
        while !Self::ptr_eq(&a, &b) {
            let next_a = a.as_ref().unwrap().borrow().next.clone();
            let next_b = b.as_ref().unwrap().borrow().next.clone();
            a = next_a;
            b = next_b;
        }
        a
    }

    fn ptr_eq(a: &Link, b: &Link) -> bool {
        match (a, b) {
            (Some(ra), Some(rb)) => Rc::ptr_eq(ra, rb),
            (None, None) => true,
            _ => false,
        }
    }

    fn list_len(head: &Link) -> usize {
        let mut count = 0;
        let mut cur = head.clone();
        while let Some(node) = cur {
            count += 1;
            cur = node.borrow().next.clone();
        }
        count
    }
}

Rust details worth knowing:

Identity, not equality. The two lists in the first example both contain a node holding 1 before the shared part, but these are different nodes. Rc::ptr_eq asks whether two pointers refer to the same allocation, which is the question the problem asks. Comparing val fields would stop too early.
saturating_sub. len_a and len_b are usize, which cannot go below zero. With two usize variables holding 3 and 5, x.saturating_sub(y) is 0, where plain x - y panics in a debug build and wraps to a huge number in an optimized one. This is why only the longer list is advanced.
Two statements per step. Writing a = a.as_ref().unwrap().borrow().next.clone(); in one line does not compile. The temporary Ref returned by borrow() is still alive at the end of the statement, so the compiler rejects the assignment with error E0506, "cannot assign to a because it is borrowed". Reading into next first lets the temporary die, and the assignment then follows.
Cloning is cheap. head_a.clone() on an Option<Rc<...>> copies one pointer and bumps a counter. With one node and one owner the count is 1, and after a clone it is 2.
while let Some(node) = cur moves cur. The body assigns cur again before the next test, so this is fine.

Complexity

Time: O(m + n). Measuring takes m + n steps. Skipping takes at most |m - n| steps, and the joint walk takes at most min(m, n) steps.

Space: O(1). The walkers are pointers, and cloning an Rc allocates nothing.

Edge cases and common mistakes

No intersection. The walkers reach None together, ptr_eq sees (None, None) and the function returns None. This also holds when the two lists have equal values but separate nodes.
Same list twice. If both heads are the same node, the lists are already aligned and the first test succeeds. The function returns the head.
Intersection at a head. When B's head is a node inside A, B has no extra nodes, A skips its extra ones, and the walkers meet on the first test.
Comparing values. Two different nodes can hold the same number. Only identity is correct.
Subtracting lengths directly. len_a - len_b underflows whenever B is the longer list.
Calling unwrap() on None. The skip loops run at most the length difference, which is smaller than the longer list, and the joint loop stops at the latest when both are None, so every unwrap() is on a real node.

Testing

A = [4, 1, 8, 4, 5] and B = [5, 6, 1, 8, 4, 5] sharing the tail 8, 4, 5 gives the node with value 8.
Two separate lists [1, 2] and [1, 2] give None.
A = [3, 9] and B = [9] where B's node is A's last node gives that node.
The same head passed twice returns the head.

Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free