Leetcode? The first common node of two linked lists

Title Description

Title address ： The first common node of two linked lists

Solution 1 ： Violence enumeration

A simple idea is to enumerate each node directly , The time complexity of doing this is O(M*N).

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        for(ListNode pa = headA; pa!=null; pa = pa.next) {
    
            for(ListNode pb = headB; pb!=null; pb = pb.next) {
    
                if(pa==pb) {
    
                    return pa;
                }
            }
        }
        return null;
    }
}

Solution 2 ： Hash set

Start from a header node and go through it , Put all nodes into a hash set , Then start traversing from another head node , Traversing to the first node in the hash set is the first node to meet .

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        Set<ListNode> set = new HashSet<ListNode>();
        ListNode temp = headA;
        while(temp!=null) {
    
            set.add(temp);
            temp = temp.next;
        }
        while(headB!=null) {
    
            if(set.contains(headB)) {
    
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

Solution 3 ： Double pointer

If both pointers are null at the beginning , Direct return null .
Two temporary pointers traverse from two header nodes respectively , After traversing to the end, return to the head node and continue down , The two temporary nodes update one step at a time , One day two nodes will meet .

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

Method four ： Double stack

Maintain two stacks , Add the elements traversed by the two head nodes to the two stacks respectively . Then start to stack at the same time , Until the elements out of the stack at the same time are different , It indicates that the last element out of the stack is the first public node .

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        ListNode pa=headA, pb=headB;
        Deque<ListNode> d1 = new ArrayDeque<ListNode>(), d2 = new ArrayDeque<ListNode>();
        while(pa!=null) {
    
            d1.add(pa);
            pa = pa.next;
        }
        while(pb!=null) {
    
            d2.add(pb);
            pb = pb.next;
        }
        ListNode ans = null;
        while(!d1.isEmpty() && !d2.isEmpty() && d1.peekLast()==d2.peekLast()) {
    
            ans = d1.pollLast();
            d2.pollLast();
        }
        return ans;
    }
}