数据结构和算法——反转单链表和判断单链表是否有环
0 / 0 / 创建于 4年前 /
Runtoweb3 的个人博客
面试算法，谈到链表，一般会考察链表的反转
思路：修改每个节点的next指针即可。创建三个变量
current:当前处理的节点
pre:当前处理的节点的前驱节点，需要赋值给current.next实现反转
nextNode:下一个要处理的节点
package main
import "fmt"
//单链表反转，对每个节点一一修改
func reverseList(l *List){
current := l.Head
var pre *Node
for current != nil{
nextNode := current.next //记录下一个修改的节点
current.next = pre//当前节点的next就是pre
pre = current //当前节点就是下一个节点的pre
current = nextNode
}
l.Head = pre
}判断单链表是否有环，有两个比较经典的思路
1.生成一个存放节点的set，遍历节点，判断节点是否在set中，不存在就把节点放入set,让后往下找。如果出现节点再set中，说明有环。
2.两个指针，一个慢指针一次移动一个节点，一个快指针一次移动2个节点。如果有环，连个指针会重合。
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：