首页 > C语言单链表求环，并返回环的起始节点

C语言单链表求环，并返回环的起始节点

若链表中存在环，找出其中的环所在的节点，否则，返回NULL

在这里插入图片描述

在没有C++ set容器的优势前提下，我们对这样的环型的寻找以及定位可以利用快慢指针来实现。

有环的存在，类似与操场跑圈，必然存在快慢之分。有了快慢，就一定会有交点。反之，有了交点，就一定存在环。

实现过程如下：

  1. slow指针移动一次，fast指针移动两次，当fast指针和slow指针相等时保留相等时的节点
  2. 根据运算，从相等时的节点和头节点以相同的速度运算，当两者相等时即为环的起始节点

在这里插入图片描述

算法实现如下：

Data *get_circle_list(Data *head) { Data *fast;Data *slow;fast  = head;slow = head;Data *meet = NULL;/*快速和慢速指针一起移动*/while (fast) { fast = fast -> next;slow = slow -> next;if (!fast) { //当快速指针为空时，即不存在环型节点return NULL;}//否则快速指针继续移动fast = fast -> next;if(fast == slow) { meet = fast;break;}}/*如果没有找到相遇的节点，那么即不存在环型*/if(meet == NULL) { return NULL;} else { while (!(head == meet)) { head = head -> next;meet = meet -> next;}return head;}return NULL;
}

源代码测试如下:

#include 
#include typedef struct link_list { int data;struct link_list *next;
}Data;void print_list(Data *head) { while (head) { printf("%d ",head->data);head = head -> next;}printf("
");
}Data *insert_head(Data *head, int n) { head = (Data *)malloc (sizeof(Data));head -> next = NULL;int data;while(n --) { Data *p = (Data *)malloc(sizeof(Data));scanf("%d",&data);p -> data = data;p -> next = head -> next;head -> next = p;}return head;
}Data *insert_tail(Data *head, int n) { head = (Data *)malloc(sizeof(Data));head -> next = NULL;Data *r = head;int data;while(n--) { Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &data);p -> data = data;r -> next = p;r = p;p -> next = NULL;}return head;
}Data *get_circle_list(Data *head) { Data *fast;Data *slow;fast  = head;slow = head;Data *meet = NULL;while (fast) { fast = fast -> next;slow = slow -> next;if (!fast) { return NULL;}fast = fast -> next;if(fast == slow) { meet = fast;break;}}if(meet == NULL) { return NULL;} else { while (!(head == meet)) { head = head -> next;meet = meet -> next;}return head;}
}int main() { /*构造环形测试用例*/Data a1,a2,a3,a4,a5,a6,a7;a1.data = 1;a2.data = 2;a3.data = 3;a4.data = 4;a5.data = 5;a6.data = 6;a7.data = 7;a1.next = &a2;a2.next = &a3;a3.next = &a4;a4.next = &a5;a5.next = &a6;a6.next = &a7;/*构造环形，这里很明显环形的起点为5节点*/a7.next = &a5;printf("get circle node 
");Data *result = get_circle_list(&a1);printf("get circle node is %d
",result -> data);return 0;
}

输出如下:

get circle node 
get circle node is 5

更多相关：

  • 剑指offer：面试题35. 复杂链表的复制

    题目：复杂链表的复制 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出...

  • leetcode-86 分隔链表

    给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 使用双指针的方式，各自构造一个大元素的头节点和小元素...

  • leetcode-142 环形链表II

    给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。 示例 1： 输入：head = [3,2,0,-4], pos = 1...

  • leetcode-92 反转链表II

    题目描述如下： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL 很明显这个题目是206 反转链表的进阶版 需要记录第m-1个节点和第n+1个...

  • leetcode-206 反转链表

    描述如下： 反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 方法一：原地反转 数据结构如下 struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}...

  • python制作统计图_刻意练习11：Python描述统计、简单统计图形

    学习计划 MyPlan11 主题：Python描述统计、简单统计图形 时间：8.5-8.11周内完成 参考资料：新书《谁说菜鸟不会数据分析python篇》 各位星友们，在这个星球里每个人都要逼迫自己学习未知的领域或知识点，每天进步一点点，积累的时间久了 ，菜鸟也能起飞。 完成情况： 在pandas中，使用describe函数进行描述统...

  • python3socket非阻塞_利用Python中SocketServer 实现客户端与服务器间非阻塞通信

    利用SocketServer模块来实现网络客户端与服务器并发连接非阻塞通信。 首先，先了解下SocketServer模块中可供使用的类： BaseServer：包含服务器的核心功能与混合（mix-in）类挂钩；这个类只用于派生，所以不会生成这个类的实例；可以考虑使用TCPServer和UDPServer。 TCPServer/UDPS...

  • 剑指offer：面试题37. 序列化二叉树

    题目：序列化二叉树 请实现两个函数，分别用来序列化和反序列化二叉树。 示例:  你可以将以下二叉树：     1    /   2   3      /     4   5 序列化为 "[1,2,3,null,null,4,5]" 解题： /*** Definition for a binary tree no...

  • sd.js 2.0封装：更加简化请求传参内容

    sd.js  import $global from "./global"; import $g from "./sg"; import $ from "jquery"; import {Message, Loading} from "element-ui";//引入饿了么相关组件 import {Base64} from "js-...

  • sd.js帮助您简化繁重的获取数据、存储数据（CRUD）骚操作（吐槽~在安卓9.0以下或者IOS10.X以下手机端H5页面不支持，在这两

        原生sd.js----------------------------------------------------------------  const API_ROOT_URL = "http://www.api.com";const $d= {_postList_url: API_ROOT_URL + "/api...

©2024 11GX.COM