[剑指offer]面试题37：两个链表的第一个公共结点

面试题37：两个链表的第一个公共结点
题目：输入两个链表，找出它们的第一个公共结点。链表结点定义如下：

struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {} };

思路:
两个链表长度分别为L1+C、L2+C， C为公共部分的长度， 第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相爱了

代码如下:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *idx1 = headA;ListNode *idx2 =headB;while(idx1!=idx2){if (idx1!=nullptr)idx1 = idx1->next;else idx1 = headB;if (idx2!=nullptr)idx2 = idx2->next;else idx2 = headA;}return idx1;}

测试用例：
● 功能测试（输入的两个链表有公共交点：第一个公共结点在链表的中间，第一个公共结点在链表的末尾，第一个公共结点是链表的头结点；输入的两个链表没有公共结点）。
● 特殊输入测试（输入的链表头结点是NULL指针）
本题考点：
● 考查应聘者对时间复杂度和空间复杂度的理解及分析能力。解决这道题有多种不同的思路。每当应聘者想到一种思路的时候，都要很快分析出这种思路的时间复杂度和空间复杂度是多少，并找到可以优化的地方。
● 考查应聘者对链表的编程能力。

总结

以上是生活随笔为你收集整理的[剑指offer]面试题37：两个链表的第一个公共结点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。