快慢指针
所谓的快慢指针的快慢是指指针向前移动的步长。比如在单链表中,快指针每次向前移动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;
}