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

本文主要是介绍《剑指 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;}
};

这篇关于《剑指 Offer》专项突破版 - 面试题 23 : 两个链表的第 1 个重合节点（C++ 实现）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---