Intersection of Two Linked Lists

Given the heads of two singly linked lists, return the node at which they intersect. If they do not intersect, return null.

Difficulty:

JavaScript Solution

function getIntersectionNode(headA, headB){
  let a = headA, b = headB;
  while(a !== b){
    a = a ? a.next : headB;
    b = b ? b.next : headA;
  }
  return a;
}

Explanation: Use two pointers. Switching heads when reaching end ensures they meet at intersection or null.

⏱ O(n + m) | 💾 O(1)

Java Solution

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

Explanation: Two pointers traverse both lists. They will meet at intersection or end at null.

⏱ O(n + m) | 💾 O(1)

Python Solution

def get_intersection_node(headA, headB):
    a, b = headA, headB
    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a

Explanation: Pointers traverse both lists. They meet at intersection or return None if no intersection.

⏱ O(n + m) | 💾 O(1)

Console

🎬 Share Your Coding Journey

Thumbnail Templates

Intersection of Two Linked Lists