题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

题目分析

长度差

先遍历一下两个链表的长度，差为 count。
让长的先走 count 步，最后再同步走，直到相遇。
时间复杂度 O(m + n)

拼接

让两个链表相互拼接，得到 A+B 和 B+A。
此时长度是相同的，可以同步进行遍历。
（代码中不需要真的做拼接，手动控制指针的遍历顺序即可）
如果链表相交，会相遇；如果不相交，会同时为null。
时间复杂度 O(m + n)

Java

public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
    int lengthA = getLength(headA);
    int lengthB = getLength(headB);

    // 确保 A 比较长
    if (lengthB > lengthA) {
        ListNode temp = headB;
        headB = headA;
        headA = temp;
    }
    int count = Math.abs(lengthA - lengthB);
    while (count > 0) {
        headA = headA.next;
        count--;
    }
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }

    return headA;
}

private int getLength(ListNode node) {
    int length = 0;
    while (node != null) {
        length++;
        node = node.next;
    }
    return length;
}

public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
    ListNode a = headA, b = headB;
    while(a != b) {
        a = a == null ? headB : a.next;
        b = b == null ? headA : b.next;
    }

    return a;
}

Kotlin

fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
    var a = headA
    var b = headB
    while (a != b) {
        a = if (a == null) headB else a.next
        b = if (b == null) headA else b.next
    }
    return a
}