7.14 Intersection of Two Linked Lists

7.14.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 160
• Difficulty: Easy
• Techniques: Two Pointers

7.14.2 Solution - Two Pointers

7.14.2.1 Walkthrough

Calculate the length of both lists. Advance the pointer of the longer list by the difference in lengths. Then traverse both lists together until they meet. Alternatively, use the two-pointer approach where we switch heads when reaching the end, effectively traversing lenA + lenB.

7.14.2.2 Analysis

• Time Complexity: O(n + m)
• Space Complexity: O(1)

7.14.2.3 Code - Java

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }
    return a;
}