`

判断两个一个链表是否存在循环(C专家编程中的问题)

阅读更多
判断两个一个链表是否存在循环(C专家编程中的问题)
#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
/**//*目的:检测指定的链表中是否存在循环*/
/**//*算法概要:同时指定p1,p2指向头节点,p1步长为1向后移,p2步长为2向后移*/
/**//*如果p1或p2指向NULL,说明不存在循环*/
/**//*如果存在循环,则p2经过循环必然会追上p1*/
/**//*算法的效率不是很高,但是却很简洁*/
/**//*author:dirtysalt,date:05.7.17,time:6:10*/
typedef struct list
{
struct list *next;
}list;
list *head=NULL,*tail=NULL;
void new_list()
{
tail=(list*)malloc(sizeof(list));
tail->next=NULL;
head=tail;
}
void add_item()
{
list *item;
item=(list*)malloc(sizeof(list));
item->next=head;
head=item;
}
void free_list()
{
list *tmp;
while(head!=tail)
{
  tmp=head;
  head=head->next;
  free(tmp);
}
free(head);
}
void make_loop()
{
tail->next=head;
}
int check_list_loop()
/**//*return value 1:loop*/
/**//*0:!loop*/
{
list *p1=head,*p2=head;
while(((p1=p1->next)!=NULL)&&((p2=p2->next)!=NULL)&&((p2=p2->next)!=NULL))
  {
   if(p1==p2)
    return 1;
  }
  return 0;
}
int main(int argc, char *argv[])
{
int i;
new_list();
for(i=0;i<10;i++)
  add_item();
if(check_list_loop()==1)
  printf("List Loop\n ");
else
  printf("List Non-Loop\n ");
make_loop();
if(check_list_loop()==1)
  printf("List Loop \n");
else
  printf("List Non-Loop\n ");
free_list();
return 0;
}
分享到:
评论

相关推荐

    循环链表数据结构C语言实现

    在C语言中,一个链表节点通常包含两个部分:数据和指向下一个节点的指针。对于循环链表,我们需要让最后一个节点的指针指向第一个节点,所以我们还需要一个指针用来记录链表的头节点。 ```c typedef struct Node { ...

    C例子:循环链表

    这通常涉及到找到两个链表的适当连接点。 9. **链表的长度**: 计算循环链表的长度不能简单地用计数器加一,因为可能会无限循环。一种解决方案是使用快慢指针,慢指针每次移动一个节点,快指针每次移动两个节点,...

    c语言 链表 双向链表 双向循环链表

    在IT领域,特别是系统编程和数据结构中,链表是一种非常基础且重要的数据结构。本文将深入探讨C语言实现的双向链表和双向循环链表,以及如何将这些概念应用于Linux内核。双向链表与单向链表相比,具有更灵活的操作...

    两个链表求交集(链表基础练习)

    解决这个问题的一种常见方法是先分别遍历两个链表,将其中一个链表(假设为较短的链表)中的所有节点存储在一个哈希表(例如Python中的字典)中。这样做的目的是为了快速检查一个节点是否存在于另一个链表中,因为...

    将两个递增的链表合并为一个非递减的链表

    本题目要求实现的功能是:输入两个递增的链表,然后通过程序对这两个链表进行排序(虽然在实际应用中,递增的链表已经有序,这里排序步骤是为了确保链表有序),接着按照递增顺序合并这两个链表,最终输出合并后的...

    循环链表和双向链表

    循环链表是一种特殊的链表结构,其特点在于链表的最后一个节点的指针域不再指向空,而是指向前一个节点,这样整个链表形成一个闭合的环形结构。在循环链表中,由于没有明显的尾端,因此在进行算法操作时需要特别注意...

    PTA 两个有序链表序列的合并

    在编程领域,有序链表序列的合并是一个常见的问题,尤其在数据结构和算法的学习中占有重要地位。这个题目“PTA 两个有序链表序列的合并”主要涉及到链表的操作和合并策略,这对于理解和掌握链表操作有极大的帮助。...

    小甲鱼 约瑟夫环问题 数据结构 C语言循环链表

    C语言中,我们可以使用结构体来定义链表节点,包含两个部分:存储人的编号的数据域和指向下一个节点的指针。 C语言循环链表的实现涉及以下几个关键点: 1. 结构体定义:创建一个结构体,如`struct Node`,包含一个...

    判断链表是否相交的几种算法1

    它通过分别遍历两个链表h1和h2,寻找h1中的节点是否出现在h2中。这种方法的时间复杂度是O(length(h1) * length(h2)),因为每次都需要遍历整个h2链表来检查是否存在匹配节点。但由于每次遍历都要遍历整个链表,所以...

    算法:给定一个链表,判断链表中是否存在环

    针对题目要求,我们可以用Python、Java和C语言实现快慢指针算法来检测链表中是否存在环。 ##### 1. Python 实现 ```python class ListNode: def __init__(self, val=0, next=None): self.val = val self.next =...

    C语言基础-C语言编程基础之Leetcode编程题解之第25题K个一组翻转链表.zip

    在C语言中,这通常通过创建两个指针,一个指向当前子链表的尾部,另一个初始为头部,然后依次交换它们指向的节点,直到两个指针相遇。 2. 初始化一个临时指针,用于保存每次翻转后子链表的前一个节点。初始时,这个...

    C语言经典但链表,C语言经典但链表,C语言经典但链表

    链表是一种基础且重要的数据结构,它在计算机科学和编程,尤其是C语言中扮演着核心角色。相较于数组,链表提供了更加灵活的数据存储方式。在本文中,我们将深入探讨链表的基本概念、类型、操作以及如何在C语言中实现...

    单循环链表(带头结点和不带头结点)

    单循环链表是一种常见的数据结构,它在计算机科学中被广泛用于存储和处理有序或无序的数据序列。链表与数组不同,不依赖于物理位置的连续性,而是通过节点间的引用连接彼此。本篇文章将深入探讨单循环链表的概念、...

    循环链表源代码

    循环链表是一种特殊的链式数据结构,其最后一个元素的指针指向了链表的第一个元素,形成一个闭合的环状结构。与线性链表不同,循环链表没有明显的起点和终点,使得在某些场景下遍历和操作更加方便。在C++编程中,不...

    链表-使用C语言实现循环链表应用之解决约瑟夫问题.zip

    在C语言中,我们首先需要定义链表节点的结构体,通常包含两个部分:数据域(用于存储元素)和指针域(指向下一个节点)。对于循环链表,最后一个节点的指针会指向链表的第一个节点,形成一个闭合的环。 以下是一个...

    双循环链表 (c++)

    在双循环链表中插入节点相对复杂,因为需要更新前后两个方向的连接。例如,在某个位置插入新节点时,需要改变新节点、前一个节点和后一个节点的指针。插入操作通常分为在头部插入、在尾部插入和在中间插入。在C++中...

    c语言链表编程实例

    ### C语言链表编程实例知识点详解 #### 1. 链表基础 链表是由一系列节点组成的集合,每个节点由数据部分和指向下一个节点的指针构成。链表的节点结构体定义如下: ```c typedef struct LNode { int data; // ...

    判断单链表中是否存在环

    3. **检测是否相遇**:通过检查两个指针是否相遇来判断链表中是否存在环。如果两个指针在某一点相遇,则表示链表中有环;如果快指针到达了链表尾部,则表示链表为无环链表。 ### 实现代码分析 在给定的部分内容中...

    双向循环链表C代码实现

    与单向链表不同,双向循环链表的每个节点都有两个指针,一个指向其前一个节点,另一个指向其后一个节点。这种结构在实现队列、栈和其他高级数据结构时非常有用。 双向循环链表的主要优点在于它的灵活性。由于我们...

Global site tag (gtag.js) - Google Analytics