【leetcode】【剑指offer Ⅱ】023. 两个链表的第一个重合节点

问题描述：

• 给定两个单链表的头节点 headA 和 headB，请找出并返回两个单链表相交的起始节点。
  • 如果两个链表没有交点，返回 null。

核心思路：

• 最直观的做法是取得较长链表 a 的长度 m 和较短链表 b 的长度 n，接着设置两个指针，处于链表 a 的指针先走 m-n 步，后续两个指针再同时步进直到相遇。
• 更简洁的做法不需要获得两个链表的长度。
  • 设置两个指针分别从链表头同时步进，只要某个指针走完链表，就将其设置到另一个链表头，最后停止条件为双指针相等。
  • 也就是说，当处于链表 a 中的指针走完全程，就将其置于链表 b 的头部继续步进。
• 可以结合代码和例子理解方法二为什么能生效：
  • 假设链 a 和链 b 重合的长度为 len_c，链 a 非重合长度为 len_a，链 b 非重合长度为 len_b，所以从链 a 出发的指针走完的路程长度为 len_a + len_c + len_b，而链 b 出发的指针走完的路程长度为 len_b + len_c + len_a。【因而最后必然会相遇】
  • 假设双链表没有重合部分，即 len_c = 0，且假设 len_a != len_b，则链 a 出发的指针走完的路程长度为 len_a + len_b，而链 b 出发的指针走完的路程长度为 len_b + len_a。【即最后同时为空指针则相遇，无论双链表长度是否相等，只要无重合，均会相遇于空指针处】

代码实现：

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