Intersection of Two Lists

Medium

Python

def get_intersection(a,b):
    pa,pb=a,b
    while pa!=pb:
        pa=pa.next if pa else b
        pb=pb.next if pb else a
    return pa

Java

public ListNode getIntersectionNode(ListNode a,ListNode b){
    ListNode pa=a,pb=b;
    while(pa!=pb){
        pa=pa!=null?pa.next:b;
        pb=pb!=null?pb.next:a;
    } return pa;
}

Key Insight

Redirect to other list at end. Equal total distance. Python vs Java ternary syntax.

Python → Java Differences

Python ternary vs Java ternary
Switch-lists trick identical
Equal total distance

Python

def get_intersection(a,b):
    pa,pb=a,b
    while pa!=pb:
        pa=pa.next if pa else b
        pb=pb.next if pb else a
    return pa

Java

public ListNode getIntersectionNode(ListNode a,ListNode b){
    ListNode pa=a,pb=b;
    while(pa!=pb){
        pa=pa!=null?pa.next:b;
        pb=pb!=null?pb.next:a;
    } return pa;
}

Algorithm Steps

1. Traverse both
2. Switch at end
3. Meet at intersection

← Previous All Linked Lists Next →