长沙做网站 青创互联,wordpress4.4.1,宁波市住房和城乡建设培训中心网站,wordpress存档显示文章所有内容点击 C 语言编程核心突破 快速C语言入门 算法: 测试链表是否有环 前言一、双指针 ( 快慢指针 )二、代码总结 前言
要解决问题: 一道简单的算法题, 测试链表是否含有环.
想到的思路: 哈希表, 将链表指针强制转换为整型, 利用求余法建立哈希函数. 太复杂, 内存效率不高… 点击 C 语言编程核心突破 快速C语言入门 算法: 测试链表是否有环 前言一、双指针 ( 快慢指针 )二、代码总结 前言
要解决问题: 一道简单的算法题, 测试链表是否含有环.
想到的思路: 哈希表, 将链表指针强制转换为整型, 利用求余法建立哈希函数. 太复杂, 内存效率不高, 经题解发现可用双指针, 即快慢指针法.
其它的补充: 简单算法题, 未看题解没做出来, 脑袋跟不上了. 一、双指针 ( 快慢指针 )
快慢指针, 就是用两个链表节点指针, 快指针每循环一次前进一个, 慢指针每循环两次前进一个, 如果有环, 快指针会套圈慢指针, 此时两指针相等, 如果没有环, 快指针会遍历完成, 并结束. #mermaid-svg-JIDsJyAN4NgloiCu {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-JIDsJyAN4NgloiCu .error-icon{fill:#552222;}#mermaid-svg-JIDsJyAN4NgloiCu .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-JIDsJyAN4NgloiCu .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-JIDsJyAN4NgloiCu .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-JIDsJyAN4NgloiCu .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-JIDsJyAN4NgloiCu .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-JIDsJyAN4NgloiCu .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-JIDsJyAN4NgloiCu .marker{fill:#333333;stroke:#333333;}#mermaid-svg-JIDsJyAN4NgloiCu .marker.cross{stroke:#333333;}#mermaid-svg-JIDsJyAN4NgloiCu svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-JIDsJyAN4NgloiCu .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-JIDsJyAN4NgloiCu .cluster-label text{fill:#333;}#mermaid-svg-JIDsJyAN4NgloiCu .cluster-label span{color:#333;}#mermaid-svg-JIDsJyAN4NgloiCu .label text,#mermaid-svg-JIDsJyAN4NgloiCu span{fill:#333;color:#333;}#mermaid-svg-JIDsJyAN4NgloiCu .node rect,#mermaid-svg-JIDsJyAN4NgloiCu .node circle,#mermaid-svg-JIDsJyAN4NgloiCu .node ellipse,#mermaid-svg-JIDsJyAN4NgloiCu .node polygon,#mermaid-svg-JIDsJyAN4NgloiCu .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-JIDsJyAN4NgloiCu .node .label{text-align:center;}#mermaid-svg-JIDsJyAN4NgloiCu .node.clickable{cursor:pointer;}#mermaid-svg-JIDsJyAN4NgloiCu .arrowheadPath{fill:#333333;}#mermaid-svg-JIDsJyAN4NgloiCu .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-JIDsJyAN4NgloiCu .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-JIDsJyAN4NgloiCu .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-JIDsJyAN4NgloiCu .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-JIDsJyAN4NgloiCu .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-JIDsJyAN4NgloiCu .cluster text{fill:#333;}#mermaid-svg-JIDsJyAN4NgloiCu .cluster span{color:#333;}#mermaid-svg-JIDsJyAN4NgloiCu div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-JIDsJyAN4NgloiCu :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} a b slow c d fast e 二、代码
#include stdbool.h
#include stdio.h
#include stdlib.h
#include string.htypedef 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语言入门
