【C++】LeetCode 160 相交链表

今天再写一道算法题（这两周都写算法题有点摆烂）

题目

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

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

注意：

1. 如果两个链表没有交点，返回 null.
2. 在返回结果后，两个链表仍须保持原有的结构。
3. 可假定整个链表结构中没有循环。
4. 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

题目链接剑指 Offer 52. 两个链表的第一个公共节点

分析

如果你像我一样，上来就怀疑这题为什么没有交叉链表的话，那你的数据结构需要恶补下了。

这是链表的定义：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
1
2
3
4
5
6
7
8

对于单链表来说，每个结点只会有1个后继，但可以有很多个前驱。因此这两个链表只要有一处公共结点，后面所有的结点就都是公共的。

此题的解法为双指针法

分别从两个链表的头指针开始，向下同步遍历，遍历完本链表后从对方链表的头指针开始，每次比较遍历到的结点，直到遍历的结点为公共结点，或者返回null代表没遍历到。

双指针法的正确性证明可以参考 LeetCode 官方的证明

代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14