考研笔试刷题第五天: 链表公共节点【链表操作】
此时我们设a的长度大于b的长度,那么肯定是p先到公共部分c,然后q在后面赶着p,那么他们走完c都不会相遇,那咋办呢?其实我们可以这样当p走完发现没有和q相遇的时候,我们让p再指向b,让q指向a,然后继续走,当p走完b,然后q走完a此时一定会相遇。我们设一个指针p指向链表a的头结点,另一个指针q指向链表b,我们让p,q两个节点分别开始运动,当a的长度等于b的长度,那么这两个节点一定会慢慢移动并移动到
·
这道题代码不难写,但是难的是思路,看下面这张图
我们设一个指针p指向链表a的头结点,另一个指针q指向链表b,我们让p,q两个节点分别开始运动,当a的长度等于b的长度,那么这两个节点一定会慢慢移动并移动到同一个节点,但是当a的长度大于b呢?又或者比a小呢?
此时我们设a的长度大于b的长度,那么肯定是p先到公共部分c,然后q在后面赶着p,那么他们走完c都不会相遇,那咋办呢?其实我们可以这样当p走完发现没有和q相遇的时候,我们让p再指向b,让q指向a,然后继续走,当p走完b,然后q走完a此时一定会相遇。为啥呢?
p的路径
a - c - b
q的路径
b - c - a
p走的总长:a+c+b
q走的总长:b+c+a
两者走的路径是一样长的。那么他们都是一步一步挪的,所以一定会相遇
这道题还有一个情况就是两个链表没有公共部分,但是按照我们这个思路其实也是成立的,会返回一个null
代码如下:
/**
* 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 *p = headA ,*q = headB;
while(p != q){
p = p? p->next : headB;
q = q? q->next : headA;
}
return p;
}
};
更多推荐
已为社区贡献2条内容
所有评论(0)