Linked list: the first coincident node of two linked lists

subject

https://leetcode-cn.com/problems/3u1WK4/
Find the first coincidence node of two linked lists

Above picture , c1 That is, two linked lists A、B The first coincident node of .

Their thinking

According to the meaning , If two linked lists are the same length , Then define the double pointer , Respectively point to the head node of the linked list , And move right at the same time , If they overlap , Then the values of the current two pointers are equal , Just go back to the node .

If the two linked lists are different , Then we need to find the length of the two linked lists first , The pointer of the linked list with longer length moves forward first delta Step , Restore the length of the linked list to the same state , Repeat the previous step , You can get the answer .

So the steps of this question are divided into two steps ：

1. Find the length of two linked lists
2. Define double pointer . First move the long linked list delta Step . Move both pointers at the same time , Until the nodes pointed to by the two pointers are equal .

Code

/** * 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) {
    
        // Count the length of two linked lists 
        int aListLength = countList(headA);
        int bListLength = countList(headB);
        // Move the long list delta Step （diff = longListLength - shortListLength）
        int delta = Math.abs(aListLength - bListLength);
     
        ListNode longerList = null;
        ListNode shortList = null;
        if(aListLength > bListLength){
    
              longerList = headA;
              shortList = headB;
        } else {
    
              longerList = headB;
              shortList = headA;
        }

        for(int i = 0; i < delta; i++) {
    
            longerList  = longerList.next;
        }

        // Move the pointer on the two linked lists at the same time , Return to the node you first met .
        while (longerList != shortList) {
    
            longerList = longerList.next;
            shortList = shortList.next;
        }
        return shortList;
    }
    
    private int countList(ListNode head) {
    
        int count = 0;
        while(head != null) {
    
            count++;
            head = head.next;
        }
        return count;
    }
}

summary

This topic examines the intersection nodes of two linked lists . The original problem can be divided into two sub problems , Find the length of the linked list and find the nodes equal to the linked list . This problem can be solved by using the speed pointer .