判断一个可能包含一个环的链表的环的开始节点

2017-01-07 08:38:02来源:CSDN作者:qq_34485658人点击

题目:给定一个可能包含一个环的链表,编写一个函数,返回环开始的节点,如果该链表不包含环,则返回NULL

分析:定义两个链表指针runner和chaser,从某个位置开始,runner以两倍速度前进,chaser以一倍速度前进,如果有环,这两个指针一定会在某处相遇,相遇时,让chaser从头结点再次出发,此时,runner和chaser都以一倍速度前进,则第二次相遇的地方就是环开始的地方(可以使用数学方法证明)


参考答案:

#include "stdafx.h"
#include<iostream>
using namespace std;

struct ListNode
{
int val;
ListNode *next;
};

ListNode *findLoop(ListNode *head)
{
if(head==NULL) return NULL;
ListNode *runner=head;
ListNode *chaser=head;

while(runner!=NULL&&runner->next!=NULL)
{
runner=runner->next->next;
chaser=chaser->next;
if(runner==chaser) break;
}
if(runner==NULL||runner->next==NULL) return NULL;
chaser=head;
while(chaser!=runner)
{
chaser=chaser->next;
runner=runner->next;
}
return chaser;
}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台