剑指offer 找两根链表的第一个公共节点

缘起

好久没做这么简单的题了 qwq

分析

题目: 输入两个链表，找出它们的第一个公共结点。

就是如果2个链表有公共节点的话, 则一定有相同的一截, 则长的链表只需要先走掉比短的链表长的长度，然后两根链表一起走，则如果有公共节点的话, 一定碰头.

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
	val(x), next(NULL) {
	}
};

class Solution {
public:
	ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
		int n=0, m=0, t; // 2根链表的长度
		ListNode* p = pHead1, *q = pHead2;
		while(p)
		{
			p = p->next;
			n++;
		} //得到链表1的长度
		while(q)
		{
			q = q->next;
			m++;
		} // 得到链表2的长度
		p = n>m?pHead1:pHead2; // p指向长的链表的头
		q = n>m?pHead2:pHead1; // q指向短的链表的头
		t = n>m?(n-m):(m-n);
		while(t--)
		{
			p = p->next;
		}
		while(p!=q)
		{
			p = p->next;
			q = q->next;
		}
		return p;
	}
};

ac情况

1
2
您的代码已保存
答案正确:恭喜！您提交的程序通过了所有的测试用例