《剑指 Offer》专项突破版 - 面试题 23 : 两个链表的第 1 个重合节点（C++ 实现）

题目链接：LCR 023. 相交链表 - 力扣（LeetCode）

题目：

输入两个单向链表，请问如何找出它们的第 1 个重合节点。例如，下图中的两个链表的第 1 个重合节点的值是 4。

分析：

首先遍历两个链表得到它们的长度，这样就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第 2 次遍历时，第 1 个指针 P1 在较长的链表中先移动若干步，再把第 2 个指针 P2 初始化为较短的链表的头节点，然后这两个指针按照相同的速度在链表中移动，直到它们相遇。两个指针相遇的节点就是两个链表的第 1 个公共节点。

例如，在上图所示的链表中，可以先各自遍历一次，得到链表的长度，分别是 6 和 5，也就是说较长的链表比较短的链表多 1 个节点。第 2 次先用一个指针 P1 在长的链表中走一步，到达值为 2 的节点。接下来把指针 P2 初始化到短的链表的头节点（值为 7 的节点）。然后分别移动这两个指针直至找到第 1 个相同的节点（值为 6 的节点），这就是我们想要的结果。这个过程如下图所示。

class Solution {
public:
 ? ?ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
 ? ? ? ?ListNode* tailA = headA,* tailB = headB;
 ? ? ? ?int countA = 1, countB = 1;
 ? ? ? ?while (tailA->next)
 ? ? ?  {
 ? ? ? ? ? ?tailA = tailA->next;
 ? ? ? ? ? ?++countA;
 ? ? ?  }
 ? ? ? ?while (tailB->next)
 ? ? ?  {
 ? ? ? ? ? ?tailB = tailB->next;
 ? ? ? ? ? ?++countB;
 ? ? ?  }
 ? ? ? ?if (tailA != tailB) ?// 说明两个链表没有重合节点
 ? ? ? ? ? ?return nullptr;
?
 ? ? ? ?int delta = abs(countA - countB);
 ? ? ? ?ListNode* longCur = headA,* shortCur = headB;
 ? ? ? ?if (countA < countB)
 ? ? ?  {
 ? ? ? ? ? ?longCur = headB;
 ? ? ? ? ? ?shortCur = headA;
 ? ? ?  }
 ? ? ? ?for (int i = 0; i < delta; ++i)
 ? ? ?  {
 ? ? ? ? ? ?longCur = longCur->next;
 ? ? ?  }
 ? ? ? ?while (longCur != shortCur)
 ? ? ?  {
 ? ? ? ? ? ?longCur = longCur->next;
 ? ? ? ? ? ?shortCur = shortCur->next;
 ? ? ?  }
 ? ? ? ?return longCur;
 ?  }
};