链表简单2 种解法

#160相交链表

按节点引用而非节点值，返回两个单链表开始相交的节点；不相交返回 null。

#链表#双指针

解题主线

长度对齐后，两指针到尾部的剩余距离相同，可同步寻找首个相同引用。

切换链表头让两指针都走 lenA + lenB 步，自动抵消长度差。

解法 1：长度对齐

先计算两链表长度，让较长链表先走长度差，再同步前进。

时间复杂度

O(m + n)

空间复杂度

O(1)

160. 相交链表 · 长度对齐

java

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

final class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengthA = length(headA);
        int lengthB = length(headB);
        ListNode first = headA;
        ListNode second = headB;
        while (lengthA > lengthB) {
            first = first.next;
            lengthA--;
        }
        while (lengthB > lengthA) {
            second = second.next;
            lengthB--;
        }
        while (first != second) {
            first = first.next;
            second = second.next;
        }
        return first;
    }

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

先计算两链表长度，让较长链表先走长度差，再同步前进。

修复较长链表为 B 时未对齐的旧实现。

解法 2：双指针换头

A 指针到尾后转向 B，B 指针到尾后转向 A，最终在交点或 null 相遇。

时间复杂度

O(m + n)

空间复杂度

O(1)

160. 相交链表 · 双指针换头

java

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

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

A 指针到尾后转向 B，B 指针到尾后转向 A，最终在交点或 null 相遇。

合并两个来源文件中的同质换头实现，只保留一次。

边界与易错点

比较的是 p1 == p2，而不是节点值相等。
旧长度法在 lenB > lenA 时仍以 lenA - lenB 为循环上界，导致未移动较长链表；必须取正的长度差。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

easy/Q160_getIntersectionNode.javaeasy/Q160_intersectionOfTwoLinkedlists.java