题解 | 链表相交-Java

import java.util.*;

public class Main {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 边界处理：如果任一链表为空，不可能有交点
        if (headA == null || headB == null) {
            return null;
        }

        // 初始化双指针，分别指向两个链表的头部
        ListNode pA = headA;
        ListNode pB = headB;

        // 循环直到两个指针相遇
        // 相遇情况有两种：1. 指向同一个交点节点 2. 都指向null（无交点）
        while (pA != pB) {
            // 当pA到达A链表末尾时，转向B链表头部继续遍历
            // 否则，pA向后移动一个节点
            pA = (pA == null) ? headB : pA.next;

            // 当pB到达B链表末尾时，转向A链表头部继续遍历
            // 否则，pB向后移动一个节点
            pB = (pB == null) ? headA : pB.next;
        }

        // 返回相遇点（可能是交点或null）
        return pA;
    }




























    //你不需要关心主函数的内容！
    public static void main(String[] args) {
        Main solution = new Main();
        Scanner scanner = new Scanner(System.in);

        // 读入数据
        int lenA = scanner.nextInt();
        int lenB = scanner.nextInt();
        int commonLen = scanner.nextInt();

        // 构建链表
        ArrayList<ListNode> nodesA = new ArrayList<>();
        ArrayList<ListNode> nodesB = new ArrayList<>();
        ArrayList<ListNode> nodesCommon = new ArrayList<>();

        // 读入并创建链表A的独立部分
        for (int i = 0; i < lenA - commonLen; i++) {
            int val = scanner.nextInt();
            nodesA.add(new ListNode(val));
            if (i > 0) nodesA.get(i - 1).next = nodesA.get(i);
        }

        // 读入并创建链表B的独立部分
        for (int i = 0; i < lenB - commonLen; i++) {
            int val = scanner.nextInt();
            nodesB.add(new ListNode(val));
            if (i > 0) nodesB.get(i - 1).next = nodesB.get(i);
        }

        // 读入并创建公共部分
        for (int i = 0; i < commonLen; i++) {
            int val = scanner.nextInt();
            nodesCommon.add(new ListNode(val));
            if (i > 0) nodesCommon.get(i - 1).next = nodesCommon.get(i);
        }

        // 连接链表
        ListNode headA = null;
        ListNode headB = null;

        if (lenA - commonLen > 0) {
            headA = nodesA.get(0);
            if (commonLen > 0) nodesA.get(nodesA.size() - 1).next = nodesCommon.get(0);
        } else if (commonLen > 0) {
            headA = nodesCommon.get(0);
        }

        if (lenB - commonLen > 0) {
            headB = nodesB.get(0);
            if (commonLen > 0) nodesB.get(nodesB.size() - 1).next = nodesCommon.get(0);
        } else if (commonLen > 0) {
            headB = nodesCommon.get(0);
        }

        // 调用函数获取结果
        ListNode result = solution.getIntersectionNode(headA, headB);

        // 输出结果
        if (result == null) {
            System.out.println("null");
        } else {
            System.out.println(result.val);
        }

        scanner.close();
    }
}