题目描述
求链表的第一个公共结点
样例
给出两个链表如下所示:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
思路:
常规思想:
本意极易联想到“蛮”方法:在第一个链表上遍历每一个结点,之后再遍历第二个链表上的每一个结点。
若找到了相同的结点,则找到了他们的公告结点。
显然这种方法的时间复杂度为O(len1*len2)
.
本题思想:
1. 求两个链表的公共结点,在求之前,可以先考虑先将两个链表的尾端对齐,
因为从第一个公共结点开始,两个链表的后面的所有结点一定是完全重合的。
2. 之后再分别得到两个链表的长度,让长的链表先进行移动,移动的距离就是两个链表的长度之差
3. 之后两个链表的头部就对齐了,这样就可以同步的进行比较,找出相同的
例如:
A: a1 → a2 → c1 → c2 → c3
B: b1 → b2 → b3 → c1 → c2 → c3
显然这种方法消耗的时间主要是求长度,所以时间复杂度为O(len1+len2)
.
C代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode* List;
int Length(List list){
int len = 0;
while(list){
len++;
list = list->next;
}
return len;
}
struct ListNode *findFirstCommonNode(struct ListNode *headA, struct ListNode *headB) {
int lenA = Length(headA);
int lenB = Length(headB);
List LongList,ShortList;//分别表示长的链表和短的链表
int dist;//表示两个链表长度之差
if(lenA < lenB){
LongList = headB;//如果链表a的长度小于b的长度,那么较长的一个就是b链表
ShortList = headA;
dist = lenB - lenA;//得到表长的差
}else{
LongList = headA;
ShortList = headB;
dist = lenA - lenB;
}
while(dist--){//先将较长的链表移动链表差值个位置
LongList = LongList->next;
}
while(LongList){
if(LongList == ShortList){
return LongList;
}else{
LongList = LongList->next;
ShortList = ShortList->next;
}
}
return NULL;
}