呼伦贝尔建设网站2021东莞封城最新消息
点击 <C 语言编程核心突破> 快速C语言入门
算法: 测试链表是否有环
- 前言
- 一、双指针 ( 快慢指针 )
- 二、代码
- 总结
前言
要解决问题: 一道简单的算法题, 测试链表是否含有环.
想到的思路: 哈希表, 将链表指针强制转换为整型, 利用求余法建立哈希函数. 太复杂, 内存效率不高, 经题解发现可用双指针, 即快慢指针法.
其它的补充: 简单算法题, 未看题解没做出来, 脑袋跟不上了.
一、双指针 ( 快慢指针 )
快慢指针, 就是用两个链表节点指针, 快指针每循环一次前进一个, 慢指针每循环两次前进一个, 如果有环, 快指针会套圈慢指针, 此时两指针相等, 如果没有环, 快指针会遍历完成, 并结束.
二、代码
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct ListNode
{int val;struct ListNode *next;
} ListNode;bool hasCycle(ListNode *head)
{if (!head){return false;}ListNode *slow = head;int num = 0;head = head->next;num++;while (head){if (head == slow){return true;}head = head->next;num++;if (num % 2 == 0){slow = slow->next;}}return false;
}
总结
只要有思路, 其实很简单, 没有思路, 则比较难.
点击 <C 语言编程核心突破> 快速C语言入门