《剑指offer》-链表的第一个公共节点

题目描述

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

这题目是指针相关的题目。初步要判断出来，有公共节点的两个指针，应当是链表后半部分相同。这样的话，当遇到第一个相同节点（不是node的val相同，而是node完全相同），则找到了结果。

网上找到一种很简介的写法。稍微分析了下，其实就是将两个链表L1和L2进行了拼接，得到L1+L2和L2+L1两个拼接结果。这两个长度相同，那么one node by one node做判断就好了。

struct ListNode{

	int val;

	struct ListNode* next;

	ListNode(int x) :val(x), next(NULL){

	}

};

class Solution_8{

public:

	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2){

		ListNode* p1 = pHead1;

		ListNode* p2 = pHead2;

		while (p1 != p2){

			if (p1 == NULL){

				cout << "p1 is NULL";

			}

			else{

				cout << "p1 is " << p1->val;

			}

			cout << ", ";

			if (p2 == NULL){

				cout << "p2 is NULL";

			}

			else{

				cout << "p2 is " << p2->val;

			}

			cout << endl;

			p1 = (p1 == NULL ? pHead2 : p1->next);

			p2 = (p2 == NULL ? pHead1 : p2->next);

		}

		return p1;

	}

};

第一眼看到这么短的代码不敢相信答案是对的。然后手动试着模拟运行了几个样例，发现是没有问题的。

第一种情况：有相同节点

L1:1 2 3 4 5

L2:3 4 5

因为两个链表每次都是移动一个步长，尽管两个链表长度往往不一样，但是L1拼接L2、L2拼接L1，这两种拼接后的链表长度是一致的，就很容易发现相同节点了。

第二种情况：没有相同节点

那么上一种情况的做法，会使得最终找到的节点是NULL，也就是分别到了“拼接后的链表尾部”。

测试一下吧：

int main_Solution_8_1(){

	ListNode* n1 = new ListNode(1);

	ListNode* n2 = new ListNode(2);

	ListNode* n3 = new ListNode(3);

	ListNode* n4 = new ListNode(4);

	ListNode* n5 = new ListNode(5);

	n1->next = n2;

	n2->next = n3;

	n3->next = n4;

	n4->next = n5;

	Solution_8 s = Solution_8();

	ListNode* res = s.FindFirstCommonNode(n1, n2);

	cout << res->val << endl;

	return 0;

}

int main_Solution_8_2(){

	ListNode* n1 = new ListNode(1);

	ListNode* n2 = new ListNode(2);

	ListNode* n3 = new ListNode(3);

	ListNode* n4 = new ListNode(4);

	ListNode* n5 = new ListNode(5);

	ListNode* n6 = new ListNode(6);

	ListNode* n7 = new ListNode(7);

	n1->next = n2;

	n2->next = n3;

	n4->next = n5;

	n5->next = n6;

	n6->next = n7;

	Solution_8 s = Solution_8();

	ListNode* res = s.FindFirstCommonNode(n1, n4);

	if (res != NULL){

		cout << res->val << endl;

	}

	else{

		cout << "res is NULL " << endl;

	}

	return 0;

}

int main(){

	main_Solution_8_2();

	return 0;

}

巴特西

《剑指offer》-链表的第一个公共节点

最新文章

热门文章