The first common node of two linked lists_ The entry of the link in the linked list (Sword finger offer)

The first common node of two linked lists

Topic link

• The first thing we think of is to let a linked list traverse the difference unit nodes first , When the length of two linked lists is equal , At the same time, if there are equal nodes, there are public nodes !

// Calculate the length difference first , Then let a pointer go the difference unit first !
public class Solution {
    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    
            ListNode cur1 = pHead1;
            ListNode cur2 = pHead2;
        int size1 = 0;
        int size2 = 0;
        while(cur1!=null){
    
            cur1 = cur1.next;
            size1++;
        }
        while(cur2!=null){
    
            cur2 = cur2.next;
            size2++;
        }
        if(size1>size2){
    
            int len = size1 - size2;
            while(len-->0){
    
                pHead1 = pHead1.next;
            }
        }else{
    
             int len = size2 - size1;
            while(len-->0){
    
                pHead2 = pHead2.next;
            }
        }
         
        while(pHead1!=null){
    
            if(pHead1.val==pHead2.val){
    
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }
}

• The above method is based on equal distance , If there are common nodes at the same speed, they will definitely meet , We can add up the two linked lists , Is the end of a linked list traversal , Just traverse from the beginning of another linked list , The same is true of another linked list , It ensures equal length , It is similar to the above method , Let's look at the dynamic diagram below !

• Through the same speed of the two pointers , We must meet each other after the same journey !
• cur1 Walk the L1,cur1 Point to L2,cur2 Walk the L2, Point to L1!

public class Solution {
    
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    
            // Definition 2 A pointer to the ! 
            // cur1  Walk the  L1, Again from  L2 Start !
            // cur2  Walk the  L2, Again from  L1 Start !
            //  Here the two pointers have the same speed , Walk the same length , If there are the same nodes, they must meet !
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while(cur1!=cur2){
    // There is no public node , Two pointers will come to null Equal exit loop !
            cur1 = (cur1==null) ? pHead2 : cur1.next;
            cur2 = (cur2 == null) ? pHead1 : cur2.next;
        }
        return cur1;
    }
}

The entry node of a link in a list

The entry node of a link in a list

• Here by defining two pointers ,slow Take a step ,fast go 2 Step , If there are rings, they will surely meet !
• Speed pointer , Through here The same time ,fast The pointer speed is slow Pointer 2 times , So is the journey 2 Times relationship !
• Through the displacement relation, the , The relationship between the entrance and the meeting point ,L = C-x The distance from the starting node to the entrance is equal to the distance from the meeting point to the ring
• Then let's find the meeting point through the speed pointer , And then go L The unit is the location of the entry node !

    public ListNode EntryNodeOfLoop(ListNode pHead) {
    
        // Speed pointer , Use the distance from the chain head to the entrance  =  The distance from the meeting point to the entrance !
        // So when the two nodes meet, they can go L Distance is the entrance position !
        // After meeting, let one of the pointers go from the chain head L, One starts at the meeting point !
        ListNode slow = pHead,fast = pHead;
        while(fast!=null&&fast.next!=null){
    // Pay attention to the conditions !!!!
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
    
                // meet !
                // Give Way slow From the beginning !
                slow = pHead;
                while(fast!=slow){
    
                    slow = slow.next;
                    fast = fast.next;
                }
                return fast;
            }
        }
        return null;
    }

• Be careful , The speed pointer here , Can only be a walk 1 Step , One goes 2 Step ! Other relationships may not guarantee meeting !