160. Intersection of Two Linked Lists


Problem Description

The problem is about finding a common intersection node (if one exists) for two singly linked lists. These lists may completely diverge, in which case no intersection occurs, or they can share a common sequence of nodes. The point at which they start to intersect becomes their intersection node. This problem does not consider linked lists with cycles and the structural integrity of the lists must remain unchanged after the function executes.

The linked list structure in question is a common data structure where each element (a node) contains data (val) and a reference (the next pointer) to the next node in the sequence. The head of a linked list refers to its first node.

We are given two heads of two singly linked lists (headA and headB), and we need to find the node from where they start intersecting.

Intuition

The challenge is to compare two singly linked lists of potentially different lengths and identify if and where they intersect. To find the intersection without extra memory for data structures like hash sets or arrays (for storing visited nodes), we can use the two-pointer technique.

Intuitively, if you traverse both lists in tandem, they will reach the intersection point at the same time if they are of the same length. However, when they're of different lengths, simply traversing them simultaneously won't work because one pointer will reach the end before the other. The key insight here is to switch lists when one pointer reaches the end. This way, both pointers end up covering the extra distance on the longer list and hence reconcile any difference in lengths.

Concretely, the solution involves two pointers, starting at headA and headB respectively. They each move forward one node at a time. When one pointer reaches the end of its list, it continues from the beginning of the other list. If there is an intersection, the pointers will meet at the intersection node after traversing lengthA + lengthB nodes (where lengthA is the length of list A including the intersection, and lengthB is the length of list B including the intersection). If there is no intersection, both pointers will eventually be null after the same number of steps, effectively also reaching the end of a hypothetically combined list.

The provided Python code prescribes this approach. It uses a simple while-loop that continues until the two pointers are equal (either at the intersection node or null). It's a concise and efficient solution as it only traverses each list once, with a time complexity of O(N + M), where N and M are the lengths of the two lists.

Solution Approach

The implementation of the solution makes use of the two-pointer technique. The algorithm involves keeping two pointers, a and b, initially set to headA and headB respectively. Both a and b traverse the respective linked lists simultaneously. If any of the pointers reaches the end of its linked list, it is reassigned to the head of the other linked list. This swapping of starting points after reaching the end ensures that the two pointers will eventually traverse equal distances even if the linked lists have different lengths.

The pseudocode of the solution is as follows:

  1. Initialize two pointers, a and b, to headA and headB respectively.
  2. While a is not equal to b:
    • If a has not reached the end of its list, move to the next node (a = a.next), otherwise, start from the beginning of headB (a = headB).
    • If b has not reached the end of its list, move to the next node (b = b.next), otherwise, start from the beginning of headA (b = headA).
  3. The loop exits when either both a and b are null (no intersection), or a and b meet at the intersection node.

In the actual implementation, here's what the critical part of the code looks like:

1while a != b:
2    a = a.next if a else headB
3    b = b.next if b else headA
4return a

This loop will keep running until a and b point to the same node. The if a else headB and if b else headA logic ensures that the pointer starts at the head of the opposite linked list upon reaching the end of its current list. If the lists do not intersect, both pointers will become null simultaneously after traversing both lists in their entirety, thus breaking the loop and returning null.

The beauty of this approach is its simplicity and the fact that it uses O(1) extra space, which is an improvement over methods that would require additional data structures to mark visited nodes.

This solution has a linear time complexity of O(N+M), where N is the length of linked list headA and M is the length of linked list headB. This is because, in the worst case, each pointer traverses both lists completely. The space complexity is O(1), as the algorithm only uses two pointers irrespective of the size of the input lists.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's assume we have two singly linked lists that intersect at some node:

  • List A: 1 -> 2 -> 3 -> 4 -> 5
  • List B: 9 -> 4 -> 5

Here, nodes with values 4 and 5 are shared among both lists, making node 4 the intersection point.

Now, we will walk through the two-pointer strategy using this example.

  1. Initialize two pointers:

    • Pointer a at the head of List A (1)
    • Pointer b at the head of List B (9)
  2. Move each pointer forward one node at a time:

    • Move a to 2, move b to 4.
  3. Continue moving forward:

    • Move a to 3, move b to 5.
    • Move a to 4, and since pointer b has no next node, it moves to the head of List A (1).
  4. Keep proceeding with the traversal:

    • Since pointer a has no next node, it moves to the head of List B (9).
    • Move b to 2.
  5. Continue the process:

    • Pointer a moves to 4, pointer b moves to 3.
  6. At this point, the crucial step occurs:

    • Pointer a is now at the node with the value 4 on List B.
    • Pointer b moves to 4 in List A (since b was previously at 3).
  7. The pointers now meet at the node with value 4, which is the intersection node.

The loop has exited because a is equal to b, signifying that the intersection node has been found. The output of our algorithm will be the node with the value 4 as it's the point of intersection.

In this example, each pointer traversed:

  • Pointer a: 1 -> 2 -> 3 -> 4 -> 1 -> 9 -> 4
  • Pointer b: 9 -> 4 -> 5 -> 1 -> 2 -> 3 -> 4

This shows that after pointer b traversed its own list, and part of List A, and pointer a traversed its own list, and part of List B, they met at the intersection node. Thus, they have traversed equal lengths, which is the basis of our algorithm – having each pointer cover the length of both lists, regardless of their initial lengths.

Python Solution

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0):
4        self.val = val
5        self.next = None
6
7
8class Solution:
9    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
10        # Initialize two pointers, one for each linked list.
11        pointerA, pointerB = headA, headB
12
13        # Continue iterating until the two pointers meet or both reach the end.
14        while pointerA != pointerB:
15            # If pointerA reaches the end, redirect it to the head of list B.
16            # Otherwise, move to the next node.
17            pointerA = pointerA.next if pointerA else headB
18
19            # If pointerB reaches the end, redirect it to the head of list A.
20            # Otherwise, move to the next node.
21            pointerB = pointerB.next if pointerB else headA
22
23        # Return either the intersection node or None if the two lists do not intersect.
24        return pointerA
25

Java Solution

1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int value; // Node value
6    ListNode next; // Reference to the next node in the list
7
8    ListNode(int x) {
9        value = x;
10        next = null;
11    }
12}
13
14public class Solution {
15    /**
16     * Find the intersection node of two singly-linked lists.
17     * An intersection node is defined as the node at which the two lists intersect.
18     *
19     * @param headA the head of the first linked list
20     * @param headB the head of the second linked list
21     * @return the intersection node or null if there is no intersection
22     */
23    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
24        ListNode pointerA = headA; // Pointer for traversing the first list
25        ListNode pointerB = headB; // Pointer for traversing the second list
26      
27        // Continue traversing until the two pointers are the same (either at intersection or both null)
28        while (pointerA != pointerB) {
29            // If we have reached the end of list A, switch to list B; otherwise, move to the next node
30            pointerA = (pointerA == null) ? headB : pointerA.next;
31            // If we have reached the end of list B, switch to list A; otherwise, move to the next node
32            pointerB = (pointerB == null) ? headA : pointerB.next;
33        }
34      
35        // At the end of the traversal, pointerA and pointerB will be either at the intersection node or null
36        return pointerA; // return the intersection node or null
37    }
38}
39

C++ Solution

1// Definition for singly-linked list.
2struct ListNode {
3    int value;
4    ListNode *next;
5    ListNode(int x) : value(x), next(nullptr) {}
6};
7
8class Solution {
9public:
10    // Function to get the node at which the intersection of two singly linked lists begins.
11    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
12        ListNode *pointerA = headA;  // Initialize a pointer for list A
13        ListNode *pointerB = headB;  // Initialize a pointer for list B
14
15        // Iterate through both lists until the two pointers meet, which means an intersection was found.
16        while (pointerA != pointerB) {
17            // If at the end of one list, move the pointer to the beginning of the other list.
18            // This ensures that each pointer traverses both lists.
19            // If at any point they meet, that's the intersection node.
20            pointerA = pointerA ? pointerA->next : headB;
21            pointerB = pointerB ? pointerB->next : headA;
22        }
23
24        // At the end of the while loop, either the intersection node or nullptr (if no intersection) is returned.
25        return pointerA;
26    }
27};
28

Typescript Solution

1/**
2 * Function to find the intersection of two singly-linked lists.
3 * 
4 * @param headA - The head of the first singly-linked list.
5 * @param headB - The head of the second singly-linked list.
6 * @returns The intersection node or null if there is no intersection.
7 */
8function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
9    // Pointers to traverse both lists
10    let pointerA: ListNode | null = headA;
11    let pointerB: ListNode | null = headB;
12
13    // Traverse both lists until the pointers meet or both reach the end (null)
14    while (pointerA !== pointerB) {
15        // If pointerA reaches the end of list A, redirect it to the head of list B
16        // This allows it to "catch up" in length to the other list on the second pass
17        pointerA = pointerA ? pointerA.next : headB;
18
19        // Similarly, if pointerB reaches the end of list B, redirect it to the head of list A
20        pointerB = pointerB ? pointerB.next : headA;
21    }
22
23    // Once both pointers meet, they are either at the intersection node or at the end (null)
24    // In either case, return the pointer as the result.
25    return pointerA;
26}
27

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(N + M), where N is the length of headA and M is the length of headB. This is because in the worst-case scenario, the code will iterate through all nodes in both lists exactly once, before either finding the intersection or reaching the end of both lists simultaneously.

Space Complexity

The space complexity of the provided code is O(1). The algorithm only uses a fixed amount of additional space for two pointers a and b, regardless of the size of the linked lists. Therefore, the space used does not scale with the size of the input.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫