链表
首先这个题目关键的地方就是,这个共同节点到底是什么。
假如有两个链表如下:
两个链表中,值为6的节点为同一节点,这就是共同节点,
但是两个链表长度不同,不能都从头遍历,
所以先找到长度差,长的链表先走,直到两个链表长度相同,再同时遍历两个链表
#include <iostream>
using namespace std;
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(nullptr) {
}
};
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
ListNode *p1 = pHead1;
ListNode *p2 = pHead2;
int len1 = 0, len2 = 0, diff = 0;
while (p1 != NULL) { //计算pHead1的长度
p1 = p1->next;
len1++;
}
while (p2 != NULL) { //计算pHead2的长度
p2 = p2->next;
len2++;
}
if (len1 > len2) { //p1放最长的链表
diff = len1 - len2;
p1 = pHead1;
p2 = pHead2;
}
else {
diff = len2 - len1;
p1 = pHead2;
p2 = pHead1;
}
for (int i = 0; i < diff; i++) { //这里的原理是,公共节点肯定在p1和p2共同长度的节点上,所以p1先走多出的diif长度,在一起判断
p1 = p1->next;
}
while (p1 != NULL && p2 != NULL) {
if (p1 == p2) {
cout << p1 ->val;
break;
}
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
void main()
{
ListNode* pHead1 = new ListNode(1);
ListNode* pt1=pHead1;
pt1->next = new ListNode(2);
pt1 = pt1->next;
pt1->next = new ListNode(3);
pt1 = pt1->next;
ListNode* root = new ListNode(2);
pt1->next = root;
pt1 = pt1->next;
pt1->next = new ListNode(1);
pt1 = pt1->next;
ListNode* pHead2 = new ListNode(4);
ListNode* pt2 = pHead2;
pt2->next = new ListNode(5);
pt2 = pt2->next;
pt2->next = root;
pt2 = pt2->next;
pt2->next = new ListNode(1);
pt2 = pt2->next;
Solution s;
s.FindFirstCommonNode(pHead1, pHead2);
}