160. Intersection of Two Linked Lists

Description

Given the heads of two singly linked-lists headA and headB, the task is to find and return the node where the two lists intersect. If the two linked lists have no intersection at all, return null.

Intuition

The key intuition behind this approach is that if two linked lists intersect, then the tail of the lists beyond the point of intersection must be the same. Therefore, the lists can be traversed in such a way that we align them starting from the intersection point.

By switching the heads of the two lists when reaching the end of one list, we can effectively equalize the lengths of the remaining parts of the lists. This ensures that the pointers will either meet at the intersection node or end up at null if there is no intersection.

Approach

1. Initialize two pointers, pointerA and pointerB, to point to headA and headB respectively.
2. Traverse through both lists using the two pointers. - If pointerA reaches the end of list A, reset it to headB. - If pointerB reaches the end of list B, reset it to headA.
3. Continue the traversal until pointerA and pointerB meet or both become null.
4. The meeting point, if any, is the intersection node. If they meet at null, there is no intersection, and the function should return null.

Complexity

Time Complexity:

O(m + n) where m and n are the lengths of the two linked lists. This is because in the worst case, both pointers traverse the entire length of both lists.

Space Complexity:

O(1). The solution only uses a constant amount of extra space.

Code

C++

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }

        ListNode *pointerA = headA;
        ListNode *pointerB = headB;

        while (pointerA != pointerB) {
            pointerA = pointerA == nullptr ? headB : pointerA->next;
            pointerB = pointerB == nullptr ? headA : pointerB->next;
        }

        return pointerA;
    }
};

Python

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None

        pointerA = headA
        pointerB = headB

        while pointerA != pointerB:
            pointerA = headB if pointerA is None else pointerA.next
            pointerB = headA if pointerB is None else pointerB.next

        return pointerA

Java

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode pointerA = headA;
        ListNode pointerB = headB;

        while (pointerA != pointerB) {
            pointerA = (pointerA == null) ? headB : pointerA.next;
            pointerB = (pointerB == null) ? headA : pointerB.next;
        }

        return pointerA;
    }
}

JavaScript

var getIntersectionNode = function(headA, headB) {
    if(headA===null || headB===null) {
        return null;
    }
    let pointerA=headA;
    let pointerB=headB;
    while(pointerA!==pointerB) {
        pointerA=pointerA===null?headA:pointerA.next;
        pointerB=pointerB===null?headB:pointerB.next;
    }
    return pointerA;

};