【面试题】-判断单链表是否有环并找到环入口(快慢指针)

时间:2022-06-14 05:21:57

快慢指针

所谓的快慢指针的快慢是指指针向前移动的步长。比如在单链表中,快指针每次向前移动2个步长,慢指针则每次向前移动1个步长。

单链表环

单链表有环的定义是链表的尾节点指向了链表中间的某个结点。比如下图。(图片来自http://www.nowamagic.net/librarys/veda/detail/2245

【面试题】-判断单链表是否有环并找到环入口(快慢指针)

解题思路

判断单链表是否有环同样利用快慢指针的原理, 设置快慢指针 *fast 、 *slow 都指向单链表的头节点, 其中 *fast 的移动速度是 *slow 的2倍。如果是有环的链表的话,快指针始终都会追上慢指针。即在循环的过程中判断两指针是否会相等,如果相等,则是。

如果判断出单链表有环,如何找到环的入口,比如上图中,D就是环的入口。假设慢指针移动了S个结点,则快指针移动了2S个结点,如果环入口离头结点为x,环入口离相遇的那个结点为y,环的长度为r,单链表总长度为L,他们的关系推导如下:

  • 2S = S + n * r (快指针的步数等于S 加上环上多转的n圈)
  • S = n * r
  • S = x + y = n * r
  • x + y = (n-1)*L + r
  • x + y = (n-1)*L + L - x
  • x = (n-1)*L + L - x - y

从最后一个式子知道,L - x - y为相遇点到环入口的距离,也就是说一个指针从头结点出发,另一个指针从相遇点出发,步长都为1的话,这两个指针一定会在环入口相遇。

代码实现

是否有环

int Is_ListLoop(LinkList L){
LinkList fast, slow;
if(L == NULL || L->next == NULL){
exit(ERROR);
}

fast = slow = L;

while(fast->next != NULL && fast->next->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(fast == slow){
printf("the List is Loop\n");
return TRUE;
}
}

printf("the List is no Loop\n");
return FALSE;

}

找到环入口

int Find_Loop(LinkList L){
LinkList fast, slow;
if(L == NULL || L->next == NULL){
exit(ERROR);
}

fast = slow = L;

while(fast->next != NULL && fast->next->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(fast == slow){
printf("the List is Loop\n");
break;
}
}

slow = L;
while(fast != slow){
slow = slow->next;
fast = fast->next;
}
printf("%d\n",slow->data );

return FALSE;

}

测试代码

测试代码中包括创建无环链表和有环链表,分别对应不同的打印链表函数。创建有环链表,第一数表示创建链表的长度,第二个表示链表尾结点指向哪个结点。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef struct Node {
int data;
struct Node *next;
} Node, *LinkList;

/*随机产生n个元素的带表头的单链表(头插法)*/
void CreatList_Head(LinkList *L, int n) {
int i;
LinkList p;
srand(time(0));

(*L) = (LinkList)malloc(sizeof(Node));
if (!(*L)) {
exit(ERROR);
}

(*L)->next = NULL;

for (i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
if (!p) {
exit(ERROR);
}
p->data = rand() % 100 + 1;
p->next = (*L)->next;
(*L)->next = p;
}
}

/*随机产生n个元素的带表头的单链表(尾插法)*/
void CreatList_Tail(LinkList *L, int n) {
LinkList p, r;
int i;

srand(time(0));

(*L) = (LinkList)malloc(sizeof(Node));
if (!(*L)) {
exit(ERROR);
}
r = (*L);

for (i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
if (!p) {
exit(ERROR);
}
p->data = rand() % 100 + 1;
r->next = p;
r = p;
}

r->next = NULL;
}

void Print_List(LinkList L) {
LinkList p;
if (!L) {
exit(ERROR);
}

p = L->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}

printf("\n");
}

void Clear_List(LinkList *L){
LinkList p,q;
if((*L) == NULL)
exit(ERROR);

p = (*L)->next;
while(p){
q = p->next;
free(p);
p = q;
}

(*L)->next = NULL;
}

void Print_List_noHead(LinkList L) {
LinkList p;
if (!L) {
exit(ERROR);
}

p = L;
while (p) {
printf("%d ", p->data);
p = p->next;
}

printf("\n");
}


int Creat_ListLoop(LinkList *L, int n, int loop_index) {

LinkList p, r,q;
int i;

srand(time(0));

(*L) = (LinkList)malloc(sizeof(Node));
if (!(*L)) {
exit(ERROR);
}
r = (*L);

for (i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node));
if (!p) {
exit(ERROR);
}
p->data = rand() % 100 + 1;
r->next = p;
r = p;
if(i == (loop_index - 1))
q = r;
}

r->next = q;

}

void Print_List_Loop(LinkList L, int n) {
LinkList p;
int i;
if (!L) {
exit(ERROR);
}

p = L->next;
for(i = 0; i < n; i++){
printf("%d ", p->data);
p = p->next;
}

printf("\n");
}

int Is_ListLoop(LinkList L){
LinkList fast, slow;
if(L == NULL || L->next == NULL){
exit(ERROR);
}

fast = slow = L;

while(fast->next != NULL && fast->next->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(fast == slow){
printf("the List is Loop\n");
return TRUE;
}
}

printf("the List is no Loop\n");
return FALSE;

}

int Find_Loop(LinkList L){
LinkList fast, slow;
if(L == NULL || L->next == NULL){
exit(ERROR);
}

fast = slow = L;

while(fast->next != NULL && fast->next->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(fast == slow){
printf("the List is Loop\n");
break;
}
}

slow = L;
while(fast != slow){
slow = slow->next;
fast = fast->next;
}
printf("%d\n",slow->data );

return FALSE;

}

int main(int argc, char const *argv[])
{
LinkList L;

CreatList_Head(&L, 11);
Print_List(L);
Is_ListLoop(L);
Clear_List(&L);
Creat_ListLoop(&L, 4, 2);
Print_List_Loop(L,8);
Is_ListLoop(L);
Find_Loop(L);
return 0;
}