Intersection of Two Linked Lists

Problem

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

Solution

Amazing Two Pointers Solution: O(n) time, O(1) space

public class Solution {
    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; //or b, anyway 
    }
}

Analysis

To prove above solution work, let's take headA = [1,2,3,4,5,6] and headB = [7,8,9,5] as example
Since headA has two nodes more than headB, b will be set to headA earlier
After two more steps, a will be set to headB and b passed two nodes already
Therefore, we guarantee that a and b will meet exactly at the intersection
If there is no intersection, they will be initially both set to null hence we will return null at the end

results matching ""

    No results matching ""