题解 | #两个链表的第一个公共结点#
两个链表的第一个公共结点
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
解题思路
分别遍历两个链表,分别求出结点个数:
若长度不等,求二者差值diff,长链表 的循环指针从头开始 先向后移动 diff 次,短链表 循环指针指向首结点,使两指针所在位置到链表尾部距离相同。
若长度相同,不做操作。
两循环指针同时向后移动,如果指向了相同结点,返回该结点元素;否则当到达尾部NULL时,表明两链表无公共部分。
代码实现
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { if(!pHead1 || !pHead2) return NULL; ListNode* p1 = pHead1; ListNode* p2 = pHead2; int count1,count2,diff; count1 = count2 =0; //计算链表1的结点总数。 while(p1){ count1++; p1=p1->next; } //计算链表2的结点总数。 while(p2){ count2++; p2=p2->next; } p1 = pHead1; p2 = pHead2; //较长链表的循环指针首先向后移动 diff 个结点。 if(count1>count2){ diff = count1-count2; while(diff>0){ p1 = p1->next; diff--; } }else{ diff = count2-count1; while(diff>0){ p2 = p2->next; diff--; } } //两个循环指针同时向后移动,指向同一结点时找到了第一个公共结点,返回。 while(p1){ if(p1==p2) return p1; p1 = p1->next; p2 = p2->next; } return NULL; //两循环指针都到达尾部,说明无公共结点 } };
时间复杂度
时间复杂度:若两链表结点总数为n,最坏情况下遍历2n个结点,故时间复杂度为O(n)。
空间复杂度:定义变量个数和输入规模无关,为O(1)。