剑指offer——JZ25 合并两个排序的链表 解题思路与具体代码【C++】

一、题目描述与要求

两个链表的第一个公共结点_牛客题霸_牛客网 (nowcoder.com)

题目描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： 0≤n≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

输入描述：

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。

返回值描述：

返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。

示例

示例1：

输入：{1,2,3},{4,5},{6,7}

返回值：{6,7}

说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分 这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

示例2：

输入：{1},{2,3},{}

返回值：{}

说明：2个链表没有公共节点 ,返回null，后台打印{}

---

二、解题思路

根据题目描述，就是两个链表在它们的尾部会有一个公共部分，我们需要找到第一个公共结点的位置，后面的结点都是公共部分。找公共结点很明显我们需要对两个链表都进行遍历，但是两个链表的长度不同，利用通俗的方法就是获取两个链表的长度，然后让长的链表先向后遍历直至两个链表长度相同，然后再两个链表同时往后遍历直至碰到第一个相同节点，这个方法简单，但是不符合题目要求的时间复杂度。

因而我们需要换一种方法。可以思考，我们可以把两个链表连接起来，这样在合并后的链表的尾部一定就是两个链表的公共部分，对此我们可以分别定义指针对两个链表进行遍历，这两个指针都需要去遍历两个链表，因为公共部分的结点数是相同的，让两个指针将两个链表各自走一遍也就是让到公共部分结点前的“步数”相同。第一遍的时候就是分别都遍历完自己链表的结点，然后就是“实现链表的连接”，让pa指针去遍历表2，让pb指针去遍历表1，在这一遍遍历中pa和pb就会指向两个表的第一个公共结点，此时返回pa/pb都行。

---

三、具体代码

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		ListNode *pa=pHead1,*pb=pHead2;
		while(pa!=pb){
			pa=(pa==NULL?pHead2:pa->next);
			pb=(pb==NULL?pHead1:pb->next);
		}
		return pa;
	}
};