题目描述
输入两个链表,找出它们的第一个公共结点。
当不存在公共节点时,返回空节点。
数据范围
链表长度 [1,2000]。保证两个链表不完全相同,即两链表的头结点不相同。
解题思路
一个比较暴力的做法当A链表和B链表的长度一致,同一个位置的指针就会移动到同一个交叉点
如果两个链表长度不一致,即使是错位,但是指针的都是由起点开始移动,当移动完一个链表,
双指针还没有相遇,那么走到头的指针再回到起点headx,再移动直到相遇(因为只有交点能相遇)
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
ListNode *ptr1 = headA;
ListNode *ptr2 = headB;
while (ptr1 != ptr2) {
if(ptr1 != NULL){
ptr1 = ptr1->next;
}else{
ptr1 = headB;
}
if(ptr2 != NULL){
ptr2 = ptr2->next;
}else{
ptr2 = headA;
}
}
return ptr1;
}
};
篇章
上一篇:AcWing 87. 把字符串转换成整数
https://www.acwing.com/solution/content/212013/
下一篇:AcWing 29. 删除链表中重复的节点(新手友好)
https://www.acwing.com/solution/content/212272/