当前位置：首页 > article >正文

【练习】【链表】力扣热题100 160. 相交链表

article 2025/3/6 0:48:30

题目

在这里插入图片描述
找相交节点。

来源：力扣热题100 160. 相交链表

思路（注意事项）

定义两个指针分别从两个端点向后遍历，如果到链表的终点还没有相遇，则让到达终点的指针指向另一条链表的起始点继续向后遍历。

原理是： 使得两个指针在找到相交节点时所移动的距离是相等的。

纯代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B)
        {
            A = A != nullptr ? A -> next : headB;
            B = B != nullptr ? B -> next : headA;
        }
        return A;
    }
};

题解（加注释）

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 定义两个指针 A 和 B，分别指向链表 headA 和 headB 的头节点
        ListNode *A = headA, *B = headB;

        // 当 A 和 B 不相遇时，继续遍历
        while (A != B)
        {
            // 如果 A 不为空，A 指向下一个节点；否则，A 指向 headB
            A = A != nullptr ? A -> next : headB;
            // 如果 B 不为空，B 指向下一个节点；否则，B 指向 headA
            B = B != nullptr ? B -> next : headA;
        }

        // 返回相遇的节点（即相交节点）
        return A;
    }
};