LeetCode - Intersection Of Two Linked Lists

Problem description

description

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.

Analysis

The first thought is to use a HashSet to store every node have seen.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        
        ListNode p1 = headA;
        ListNode p2 = headB;
        
        while (p1 != null || p2 != null){
            if (p1 == null){
                if(set.contains(p2)){
                    return p2;
                }
                
                set.add(p2);
                
                p2 = p2.next;
            }
            else if (p2 == null){
                if (set.contains(p1)){
                    return p1;
                }
                
                set.add(p1);
                
                p1 = p1.next;
            }
            else{
                if (set.contains(p1)){
                    return p1;
                }
                set.add(p1);
                
                p1 = p1.next;
                
                
                if (set.contains(p2)){
                    return p2;
                }
                set.add(p2);
                
                p2 = p2.next;
            }
        }
        
        return null;
    }
}

However, there’s a better solution from LeetCode, we can start from the head of another list if we reach the end.

Suppose we have two lists, and the common part is marked as C. Then we have:

A - C - B - C

B - C - A - C

So that we can know that the first intersection one is the C.

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

What to improve

• we can use the observation to check intersection in O(1) SC.