160. Intersection of Two Linked Lists

Problem Statement

Pattern:

---

Solution

Works even if no intersection

public ListNode getIntersectionNode (ListNode headA, ListNode headB){
	int lenA = getLen(headA), lenB = getLen(headB);
	while(lenA > lenB){
		headA = headA.next;
		lenA--;
	}
	while(lenB > lenA) {
		headB = headB.next;
		lenB--;
	}
	
	while(headA != headB) {
		headA = headA.next;
		headB = headB.next;
	}
	return headA;   // returns null if no intersection found
}
 
private int getLen (ListNode head) {
	if(head == null) return 0;
	int count = 1;
	while(head.next != null) {
		head = head.next;
		count++;
	}
	return count;
}

Notes

• find difference in lengths in linked lists

• shift the longer lls pointer fwd by the diff

• now when you increment both pointers they will intersect at the intersection.

• return a pointer

• if intersection not found, null will be returned

Clever Solution

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //boundary check
    if(headA == null || headB == null) return null;
    
    ListNode a = headA;
    ListNode b = headB;
    
    //if a & b have different len, then we will stop the loop after second iteration
    while( a != b){
    	//for the end of first iteration, we just reset the pointer to the head of another linkedlist
        a = a == null? headB : a.next;
        b = b == null? headA : b.next;    
    }
    
    return a;
}

Java solution without knowing the difference in len! - LeetCode Discuss

• here instead of checking lenths, as as soon as one LL’s pointer reaches the end, set it to the head of the other LL.

• once both LL’s , have reached the end, and swapped to the other’s start’s the longer one would have offset by the difference in lengths!

• once they intersect, return any pointer

• if intersection is not found, both will reach end together(since we fixed the offset) and null will be returned!

it’s a perfect solution