Intersection of Two Linked Lists, thesarfo

Given two singly linked lists, return the node at which they intersect, or null if they don’t. (LeetCode 160)

Brute force (nested loops): for every node in list A, scan every node in list B checking for reference equality.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        while (headA != null) {
            ListNode temp = headB;
            while (temp != null) {
                if (headA == temp)
                    return headA;
                temp = temp.next;
            }
            headA = headA.next;
        }
        return null;
    }
}

Time: O(m × n). Space: O(1).

Better — hashing: store every node from list A in a HashSet, then walk list B and return the first node found in the set.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();

        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }

        while (headB != null) {
            if (set.contains(headB)) return headB;
            headB = headB.next;
        }

        return null;
    }
}

Time: O(m + n). Space: O(m).

Optimal — two pointers: walk both lists in lockstep; when a pointer hits the end, redirect it to the head of the other list. The first pointer travels a + c then b (total a + c + b); the second travels b + c then a (total b + c + a) — equal totals, so they meet at the intersection (or both hit null together if there isn’t one).

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;

        while (a != b) {
            a = (a != null) ? a.next : headB;
            b = (b != null) ? b.next : headA;
        }

        return a;
    }
}

Time: O(m + n). Space: O(1).