Intersecting linked list (set, double pointer)

Topic link ：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

subject ： Here are two head nodes of the single linked list headA and headB , Please find out and return the starting node where two single linked lists intersect . If two linked lists do not have intersecting nodes , return null .

Method 1 ：Set aggregate

Their thinking ：1.Set aggregate

Let's go through the linked list first A, take A All nodes of the linked list are put into one set in .
And then I'll go through it B Linked list , If B A node of the linked list appears in set in , Returns the first node of the intersection .

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        //Set aggregate 
        Set s = new HashSet();
        ListNode p = headA;//p Pointer control linked list A
        ListNode q = headB;//q Pointer control linked list B
        while(p != null){
    
            s.add(p);
            p = p.next;
        }
        while(q != null){
    
            if(s.contains(q)) return q;
            q = q.next;
        }
        return null;
    }
}

Method 2 ： Double pointer

Their thinking ：2. Double pointer

First, pre judgment , Judgment list headA and headB Is it empty , If at least one linked list is empty , Then the two linked lists must not intersect , return null.

Here we will discuss it according to the situation , It is divided into two linked lists intersecting and two linked lists not intersecting .

Two linked lists intersect ：

Suppose the linked list headA and headB The lengths of are m and n, Suppose the linked list headA The disjoint parts of are a Nodes , Linked list headB The disjoint parts of are b Nodes , The intersecting part of the two linked lists is c Nodes , Then there are a+c=m,b+c=n. here , It is divided into a==b And a!=b The situation of .

a==b when , The two pointers reach the first intersecting node at the same time , Just output

a!=b, It is impossible for the pointer to reach the tail at the same time when traversing the node for the first time , When Pa == null when ,Pa Point to headB; When Pb == null when ,Pb Point to headA, So when Pa Move a+c+b Next time ,Pb Move b+c+a Next time , The two pointers met for the first time , That is, the first intersection of the two linked lists .

The two linked lists do not intersect ：

Suppose the linked list headA and headB The lengths of are m and n, consider m==n and m!=n The situation of .

m==n when , Then the two pointers will reach the tail node of the two linked lists at the same time , At the same time, it is equal to null, Is out of while loop , Output null.

m!=n when , Because the two linked lists have no common nodes , Two pointers will not reach the tail node of two linked lists at the same time , Therefore, both pointers will traverse the two linked lists , At the pointer a Moved m+n Time 、 The pointer b Moved n+m After that , Both pointers will become null at the same time null, Return at this time null.

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        if(headA == null || headB == null) return null;
        ListNode a = headA;
        ListNode b = headB;
        while(a != b){
    
            a = (a != null)?a.next:headB;
            b = (b != null)?b.next:headA;
        }
        return a;
    }
}