题解 | 链表相交

import java.util.*;

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

    public int getLen(ListNode head){
        int len = 0;
        while(head!=null){
            len++;
            head = head.next;
        }
        return len;
    }

    public ListNode is_Judge(int n,ListNode a,ListNode b){
        //默认a比b长
        while(n-->0){
            a = a.next;//与b对齐
        }
        ListNode res = null;
        while(a!=null&&b!=null){
            if(a.val==b.val){
                res = a;
                while(a!=null&&b!=null&&a.val==b.val){
                    a = a.next;
                    b = b.next;
                }
            }else{
                a = a.next;
                b = b.next;
                res = null;
            }
        }
        return res;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       int len_a = getLen(headA);
       int len_b = getLen(headB);
       if(len_a>len_b){
        return is_Judge(len_a-len_b,headA,headB);
       }
       else if(len_a<len_b){
        return is_Judge(len_b-len_a,headB,headA);
       }
       else{
        return is_Judge(0,headA,headB);
       }
    }

    



























    //你不需要关心主函数的内容！
    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();
    }
}