[leetcode] intersecting linked list

#LeetCode A daily topic 【 Special topic of linked list 】

• Intersecting list
  https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

• analysis
  The ring linked list has been implemented , How to find the position of the ring . This problem can be regarded as a derivative of the circular linked list , Find the location where the linked list intersects ：

  1. Construct a ring ,headA A round of traversal , End to end connection ring
  2. At this point is a circular linked list to find the location of the ring ： Use double pointer , After a quick and slow encounter , Reset the slow pointer to the starting point and start again at the same time , When they meet, they are in the ring position ： See ：
     https://blog.csdn.net/shijiujiu33/article/details/122544237
  3. It should be noted that , The title requires to keep the original linked list structure unchanged , After finding the intersection , Ring break required

• Realization

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        //  Find the location where two linked lists meet 
        //  Similar to circular linked list , Find the location of the ring 
        //  First traversal , take A Linked lists form rings ; Then there is the problem of a circular linked list 
        // A Two steps at a time ,B One step at a time ; After meeting , Set one of them as the head node , Walking at the same time , The second meeting is the position of entering the ring （ Intersection location ）

        if (headA == null || headB == null) {
    
            return null;
        }

        ListNode temp = headA;
        while (temp.next != null) {
    
            temp = temp.next;
        }
        temp.next = headA;

        ListNode left = headB, right = headB;
        while (right != null && right.next != null) {
    
            right = right.next.next;
            left = left.next;
            if (left == right) {
    
                break;
            }
        }
        left = headB;
        while (right != null && right.next != null) {
    
            if (left == right) {
    
                //  Broken ring （ Keep the original structure unchanged ）
                temp.next = null;
                return left;
            }
            left = left.next;
            right = right.next;
        }
        //  Broken ring （ Keep the original structure unchanged ）
        temp.next = null;
        return null;
    }

LeetCode Time consuming ：1ms

• Achieve two
  Alternate traversal ,headA After traversing , from headB To traverse the ; meanwhile headB After traversing , from headA To traverse the , Then the position where they meet is determined as the intersection point ：
  It's also a math problem

public ListNode getIntersectionNode02(ListNode headA, ListNode headB) {
    
        //  Alternate traversal ,headA After traversing , from headB To traverse the ; meanwhile headB After traversing , from headA To traverse the , Then the position where they meet is determined as the intersection point 
        if (headA == null || headB == null) {
    
            return null;
        }
        ListNode tempA = headA, tempB = headB;
        //  There is no intersection , Will be in null=null meet 
        while (tempA != tempB) {
    
            tempA = tempA == null ? headB : tempA.next;
            tempB = tempB == null ? headA : tempB.next;
        }
        return tempA;
    }

LeetCode Time consuming ：1ms

• summary
  Be good at changing topics into familiar ones ;
  The position of the intersection can be converted to the position of the finding ring ;