我是靠谱客的博主 和谐音响,最近开发中收集的这篇文章主要介绍C实现 LeetCode->Linked List Cycle 双指针大法)(单链表是否有环 并计算环长度),觉得挺不错的,现在分享给大家,希望可以做个参考。
概述
1.如何判断是否有环?如果有两个头结点指针,一个走的快,一个走的慢,那么若干步以后,快的指针总会超过慢的指针一圈。
2.如何计算环的长度?第一次相遇(超一圈)时开始计数,第二次相遇时停止计数。
3.如何判断环的入口点:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。
//
//
LinkedListCycleII.c
//
Algorithms
//
//
Created by TTc on 15/6/22.
//
Copyright (c) 2015年 TTc. All rights reserved.
//
/**
*
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
上题的升级版。
只要搞清楚规律就好办了。
方法是当两个指针重合后,把其中一个指针回归第一个结点,然后两个同时走,当再次相遇时就使圆环的开始点。
*/
#include "LinkedListCycleII.h"
#include <stdbool.h>
#include <stdlib.h>
#include "Clist.h"
/********************************************************************/
// LeetCode
/********************************************************************/
struct ListNode {
int val;
struct ListNode *next;
};
//判断一个链表是否为 循环链表;
双指针大法(一快一慢)
//如果有两个头结点指针,一个走的快,一个走的慢,那么若干步以后,快的指针总会超过慢的指针一圈。
struct ListNode *
detectCycle(struct ListNode *head) {
if(head == NULL) return NULL;
struct ListNode *iter1 = head;
struct ListNode *iter2 = head;
while(true){
if(!iter1 || !iter2) return NULL;
iter1 = iter1->next;
if(iter1 != NULL) iter1 = iter1->next;
/*每次 iter1 自增两次,走2步*/
else return NULL;
//每次iter2 自增一次,走一步
iter2 = iter2->next;
/*判断是否两个指针重合点*/
if(iter1 == iter2) {
iter2 = head;
while(iter1 != iter2){
iter1 = iter1->next;
iter2 = iter2->next;
}
return iter1;
}
}
}
/********************************************************************/
/********************************************************************/
/********************************************************************/
// List.c 是范性类 单链表
/********************************************************************/
//如果有两个头结点指针,一个走的快,一个走的慢,那么若干步以后,快的指针总会超过慢的指针一圈。
CListElmt *
tt_detectCycle(CListElmt *head) {
if(head == NULL) return NULL;
CListElmt *iter1 = head;
CListElmt *iter2 = head;
while(true){
if(!iter1 || !iter2) return NULL;
iter1 = iter1->next;
if(iter1 != NULL) iter1 = iter1->next;
/*每次 iter1 自增两次,走2步*/
else return NULL;
//每次iter2 自增一次,走一步
iter2 = iter2->next;
/*判断是否两个指针重合点*/
if(iter1 == iter2) {
iter2 = head;
while(iter1 != iter2){
iter1 = iter1->next;
iter2 = iter2->next;
}
return iter1;
}
}
}
void
test_tt_detectCycle(){
CList l1;
clist_init(&l1, free);
int *data ;
int array[15] = {100,200,300,400,500,600,700,800,900,1000};
for (int i = 0; i< 5; i++) {
if ((data = (int *)malloc(sizeof(int))) == NULL)
return ;
*data = array[i];
if (clist_ins_next(&l1, clist_head(&l1), data) != 0)
//逐个插入元素
return;
}
printf("clist.size===>%dn",clist_size(&l1));
cprint_list(&l1);
CListElmt *result = tt_detectCycle(clist_head(&l1)->next);
printf("result===%dn",*(int *)result->data);
}
最后
以上就是和谐音响为你收集整理的C实现 LeetCode->Linked List Cycle 双指针大法)(单链表是否有环 并计算环长度)的全部内容,希望文章能够帮你解决C实现 LeetCode->Linked List Cycle 双指针大法)(单链表是否有环 并计算环长度)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复