（单链表备忘记录）
知识点：
- 单链表结构
- 创建链表方法
- 头插法创建
- 尾插法创建
- 遍历链表
- 逆序反转链表
- 迭代
- 递归
- 头插法
- 就地逆置
- 判断链表中是否有环
- 链表中环的入口点
- 链表中环的长度
- 链表总长度
1. 单链表结构
data. 数据
next. 指向下一个链表节点的指针
type Node struct {
data int
next *Node
}
2. 创建链表方法
简单的可以一行行敲着创建，先创建node1，然后node2,
然后链起来node1.next=&node2
1. 头插法创建
/*头插法 创建链表*/
func CreateNodeInsterOnHead(listData []int) *Node {
if len(listData) == 0 {
return &Node{data: 0}
}
head := &Node{data: listData[0]}
for _, v := range listData[1:] {
node := &Node{data: v}
node.next = head //新节点的next指向头head
head = node//头head换成新节点
}
return head
}
传入 「1 2 3 4 5 6 7 8 9 10」
输出 「10 9 8 7 6 5 4 3 2 1」
2. 尾插法创建
/*尾插法创建链表*/
func CreateNodeInsterOnTail(listData []int) *Node {
if len(listData) == 0 {
return &Node{data: 0}
}
head := &Node{data: listData[0]}
end := head //end 记录链表的尾，不断向end后插入新节点
for _, v := range listData[1:] {
end.next = &Node{data: v}
end = end.next //移动end指针，指向新的尾节点
}
return head
}
传入 「1 2 3 4 5 6 7 8 9 10」
输出 「1 2 3 4 5 6 7 8 9 10」
3. 遍历链表
func printNode(node *Node) {
if node == nil || node.next == nil {
return
}
cur := node
for cur != nil {
fmt.Printf("%d ", cur.data)
cur = cur.next
}
}
4. 逆序反转链表
4.1 迭代
func ReverseNode1(head *Node) *Node {
if head == nil || head.next == nil {
return head
}
var prev *Node = nil
var cur *Node = head
var end *Node = head.next
for {
cur.next = prev //当前结点指向前一个节点
if end == nil {
break
}
prev = cur //指针后移
cur = end //指针后移，处理下一个节点
end = end.next //temp作为中间节点，记录当前结点的下一个节点的位置
}
head = cur
return head
}
4.2 递归
func ReverseNode2(head *Node) *Node {
if head == nil || head.next == nil {//递归的出口
return head
} else {
//一直递归，找到链表中最后一个节点
new_head := ReverseNode2(head.next)
//当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
//递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。
//每退出一层，都需要改变 head->next 节点指针域的指向，同时令 head 所指节点的指针域为 NULL。
head.next.next = head
head.next = nil
//每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
return new_head
}
}
4.3 头插法
func ReverseNode3(head *Node) *Node {
var new_head *Node = nil
var temp *Node = nil
if head == nil || head.next == nil {
return head
}
for head != nil {
temp = head
//将 temp 从 head 中摘除
head = head.next
//将 temp 插入到 new_head 的头部
temp.next = new_head
new_head = temp
}
return new_head
}
4.4 就地逆置
func ReverseNode4(head *Node) *Node {
var beg *Node = nil
var end *Node = nil
if head == nil || head.next == nil {
return head
}
beg = head
end = head.next
for end != nil {
//将 end 从链表中摘除
beg.next = end.next
//将 end 移动至链表头
end.next = head
head = end
//调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
end = beg.next
}
return head
}
5. 判断链表中是否有环
快慢指针
/*
* 链表是否有环
* is 是否
* meet 有环是返回快慢指针的相遇节点
*/
func isRingLinkNode(head *Node) (is bool, meet *Node) {
slow := head
fast := head
for fast != nil && fast.next != nil {
slow = slow.next
fast = fast.next.next
if slow == fast {
return true, slow
}
}
return false, nil
}
6. 链表中环的入口点
func findRingeEntry(head *Node) *Node {
slow := head
fast := head
for fast != nil && fast.next != nil {
slow = slow.next
fast = fast.next.next
if slow == fast {
break
}
}
if fast == nil || fast.next == nil {
return nil
}
slow = head //慢指针重新指向头节点
for slow != fast {
slow = slow.next
fast = fast.next
}
return slow
}
相遇后，slow继续一次移动一个节点，新另一node从链表头开始一次移动一个节点。
7. 链表中环的长度
//计算单链表环的长度
func ringLength(head *Node) int {
//首先通过上面的方法判断，链表是否有环，并返回快慢指针的相遇点
is, meet := isRingLinkNode(head)
if is == false {
return 0 //没有环，则直接返回
}
tmp := meet //tmp 停留在相遇点不再移动
meet = meet.next
len := 1
for tmp != meet {
len++
meet = meet.next
}
return len
}
先用快慢指针相遇，相遇后记录相遇点，然后继续next向下走并记录走了几步，
再次相遇时即环长度。
8. 链表总长度
总长度 = 头到入口点长度 + 环到长度
