12、Lecode：52 两个链表的第一个公共节点(双指针，我们只跑一遍先让其变为同样长)

输入两个链表，找出它们的第一个公共节点。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

package com.example.lecode.chainTable;



import lombok.extern.log4j.Log4j2;



/**

 * 输入两个链表，找出它们的第一个公共节点。

 * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

 * 输出：Reference of the node with value = 8

 * 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。

 * 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

 */

@Log4j2

public class getIntersectionNode {

    public static void main(String[] args) {

        ListNode headA = new ListNode(4);

        headA.next = new ListNode(1);

        headA.next.next = new ListNode(8);

        headA.next.next.next = new ListNode(4);

        headA.next.next.next.next = new ListNode(5);



        ListNode headB = new ListNode(5);

        headB.next = new ListNode(0);

        headB.next.next = new ListNode(1);

        headB.next.next.next =  headA.next.next;



        getIntersectionNode solution = new getIntersectionNode();

        ListNode newHead = solution.getIntersectionNode(headA, headB);



        // 输出链表的值

        while (newHead != null) {

            System.out.print(newHead.val + " ");

            newHead = newHead.next;

        }

    }



    /**

     * 计算链表的长度是为了确定两个链表剩余部分的长度是否相等。

     * 在双指针法中，我们需要让较长的链表先移动多出的长度，使得两个链表剩余的长度相等，然后再同时在两个链表上移动指针。

     * 通过计算链表的长度，我们可以得到链表 A 和链表 B 的长度差。然后，

     * 我们让较长链表的指针先移动这个长度差的步数，使得剩余部分的长度相等。

     * 这样做的目的是为了保持两个指针在剩余部分的起点位置是对齐的。

     * 然后，我们同时在两个链表上移动指针，直到找到第一个相等的节点，即为它们的第一个公共节点。

     * 这是因为在移动相同的步数后，两个指针会到达相同的位置，如果存在公共节点，它们就会相遇。

     * 所以，计算链表的长度是为了在双指针移动之前，将较长链表的指针移动到合适的位置，使得两个链表剩余部分的长度相等，从而能够同时移动指针查找公共节点。

     * @param headA

     * @param headB

     * @return

     */

    ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if(headA == null || headB == null){

            return null;

        }



        ListNode nodeAa = headA;

        ListNode nodeBb = headB;



        int lenA = 0;

        int lenB = 0;

        while(nodeAa != null){

            lenA ++;

            nodeAa = nodeAa.next;

        }



        while(nodeBb != null){

            lenB ++;

            nodeBb= nodeBb.next;

        }



        while(lenA > lenB){

            headA = headA.next;

            lenA--;

        }



        while(lenB > lenA){

            headB = headB.next;

            lenB--;

        }



        while(headA != headB){

            headA = headA.next;

            headB = headB.next;

        }

        return headA;

    }

}