LeetCode 160链表相交问题：双指针解法超时原因咨询

问题描述 #

给定两个单链表的头节点headA和headB，返回两链表相交的节点；若两链表无相交则返回null。测试用例保证整个链表结构无环，且函数返回后需保留链表原结构。

你的错误解法（超时且破坏链表结构） #

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *tempA = headA, *tempB = headB;
    while (tempA != tempB) {
        if (tempA->next != NULL) { tempA = tempA->next;}
        else { tempA->next = headB;}
        if (tempB->next != NULL) { tempB = tempB->next;}
        else { tempB->next = headA; }
    }
    return tempA;
}

正确解法 #

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *tempA = headA, *tempB = headB;
    while (tempA != tempB) {
        if (tempA != NULL) { tempA = tempA->next;}
        else { tempA = headB;}
        if (tempB != NULL) { tempB = tempB->next;}
        else { tempB = headA;}
    }
    return tempA;
}

两者的核心差异分析 #

1. 指针移动的判断逻辑完全不同

   • 错误解法判断tempA->next != NULL，当指针走到链表最后一个节点时，会修改该节点的next指向另一个链表的头，直接破坏原链表结构，违反题目要求。
   • 正确解法判断tempA != NULL，当指针走到链表末尾的null时，直接跳转到另一个链表的头，全程不修改任何节点的next指针，完美保留原链表结构。

2. 不相交场景的处理导致超时

   • 当两链表不相交时，错误解法会把两个链表的尾节点互相指向对方的头，形成循环链表。此时两个指针会在循环里无限遍历，永远不会相等，触发Time Limit Exceeded。
   • 正确解法中，两个指针各自走完自己的链表后，会去走对方的链表，总路程都是len(A)+len(B)，最终会同时走到null，循环退出返回null，不会死循环。

3. 对题目规范的遵守程度不同
   错误解法直接修改原链表的节点指针，违反了“返回后保留链表原结构”的要求；正确解法仅移动指针遍历，未对原链表做任何修改，完全符合题目规范。

内容的提问来源于stack exchange，提问作者Deming Cheng