52.两个链表的第一个公共节点

参考链接

剑指offer_在线编程_牛客网

剑指 Offer 52. 两个链表的第一个公共点-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

LCR 171. 训练计划 V - 力扣（LeetCode）

个人尝试

先用指针遍历两个链表，求得两个链表的长度 lenA、lenB，

随后，计算两个链表长度之差 dif = abs(lenA-lenB)，

接着，长度较长链表的先开始遍历 dif 个节点后，两个链表再开始一起遍历。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode tmpA = headA;
        ListNode tmpB = headB;
        int couA = 0;
        while(tmpA != null) {
            couA++;
            tmpA = tmpA.next;
        }
        int couB = 0;
        while (tmpB != null) {
            couB++;
            tmpB = tmpB.next;
        }
        // 设定 couA 较大
        if (couA < couB) {
            int tmp = couA;
            couA = couB;
            couB = tmp;

            tmpA = headB;
            tmpB = headA;
        } else {
            tmpA = headA;
            tmpB = headB;
        }

        int dif = couA - couB;
        while (tmpA != null && tmpB != null) {
            if (tmpA == tmpB) return tmpA;

            tmpA = tmpA.next;
            if (dif > 0) {
                dif--;
                continue;
            }
            tmpB = tmpB.next;
        }
        return null;
    }
}

优秀题解

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solutions/627084/jian-zhi-offer-52-liang-ge-lian-biao-de-gcruu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码精简了好多！

设公共节点为 node，两链表的公共长度为 c

指针 pointA，遍历一遍链表 A，随后遍历链表 B 的非公共节点，总长度为 lenA + lenB - c，

指针 pointB ，遍历一遍链表 B，随后遍历链表 A 的非公共节点，总长度为 lenB + lenA - c，

此时有 lenA + lenB - c = lenB + lenA - c，

倘若，链表 AB 有公共节点，则 指针 pointA、pointB 指向同一节点；

倘若，链表 AB 没有公共节点，则 指针 pointA、pointB 指向 null。