algoadvance

Leetcode 160. Intersection of Two Linked Lists

Problem Statement

Given the heads of two singly linked lists, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return nullptr.

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

List A:       a1 → a2
                       ↘
                         c1 → c2 → c3
                       ↗
List B:  b1 → b2 → b3

Example 1:

Input: IntersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 8 if they don't 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: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2. 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: Reference of the node with value = 0
Input Explanation: The two lists do not intersect, so intersected node lockup returns null.

Note:

Clarifying Questions

  1. What can we assume about the structure of the input lists?
    • They are singly linked lists with nodes containing at least a value and a pointer to the next node.
  2. Should we modify the lists in-place?
    • No, we should not alter the input lists.
  3. Are the input lists guaranteed to intersect?
    • No, the lists might not intersect which means the return should be nullptr.
  4. Can the structure of the lists form any cycles, or are they guaranteed to be acyclic?
    • They are guaranteed to be acyclic.

Strategy

Our approach leverages the two-pointer technique to find the intersection node of two linked lists efficiently. The strategy works by balancing the lengths of both lists:

  1. Initialize two pointers ptrA and ptrB to the heads of listA and listB respectively.
  2. Traverse through the lists and at the end of each traversal — if any pointer reaches the end of a list, redirect it to the head of the other list.
  3. If the two pointers meet at a node, that node is the intersection.
  4. If they do not meet and have traversed both lists completely (both are nullptr), there is no intersection.

Code

#include <cstddef>

// Definition for singly-linked list node.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) return nullptr;
        
        ListNode* ptrA = headA;
        ListNode* ptrB = headB;
        
        while (ptrA != ptrB) {
            ptrA = (ptrA != nullptr) ? ptrA->next : headB;
            ptrB = (ptrB != nullptr) ? ptrB->next : headA;
        }
        
        return ptrA;
    }
};

Time Complexity

The time complexity of this algorithm is O(m + n), where m and n are the lengths of listA and listB respectively.

This complexity arises because each list is traversed exactly twice in the worst case (once fully traversing its own list, and once traversing the other list if no intersection is found earlier).

The space complexity is O(1) because no additional space is used except for the pointers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI