intersectionOfTwoLinkedLists

160. 相交链表

分析

初始化指针
- 定义两个指针 p 和 q，分别指向链表 headA 和 headB 的头节点
遍历链表
- 让两个指针同时遍历各自的链表，当某个指针到达链表尾部时，切换到另一个链表的头节点继续遍历
终止条件
- 如果链表相交，p 和 q 会在相交节点相遇，此时返回相交节点
- 如果链表不相交，两个指针会同时变为 null，退出循环并返回 null
关键点
- 当一个指针遍历完自己的链表后，切换到另一个链表，从而保证两个指针在第二次遍历时长度相同
- 这样，当两链表有相交节点时，两个指针在第二次遍历中必定会在相交节点处相遇

时间复杂度

指针最多遍历两个链表一次，两个链表的长度分别为 m 和 n，总时间复杂度 O(m + n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        ListNode *p = headA, *q = headB; // 初始化两个指针 p 和 q
        while (p != q)                  // 当 p 和 q 不相等时继续循环
        {
            p = p ? p->next : headB;    // 如果 p 非空，移动到下一个节点，否则切换到 headB
            q = q ? q->next : headA;    // 如果 q 非空，移动到下一个节点，否则切换到 headA
        }
        return p;                       // 返回相交节点或 null
    }
};