（單鏈表備忘記錄）
知識(shí)點(diǎn)：
- 單鏈表結(jié)構(gòu)
- 創(chuàng)建鏈表方法
- 頭插法創(chuàng)建
- 尾插法創(chuàng)建
- 遍歷鏈表
- 逆序反轉(zhuǎn)鏈表
- 迭代
- 遞歸
- 頭插法
- 就地逆置
- 判斷鏈表中是否有環(huán)
- 鏈表中環(huán)的入口點(diǎn)
- 鏈表中環(huán)的長度
- 鏈表總長度
1. 單鏈表結(jié)構(gòu)
data. 數(shù)據(jù)
next. 指向下一個(gè)鏈表節(jié)點(diǎn)的指針
type Node struct {
data int
next *Node
}
2. 創(chuàng)建鏈表方法
簡單的可以一行行敲著創(chuàng)建，先創(chuàng)建node1纪吮，然后node2,
然后鏈起來node1.next=&node2
1. 頭插法創(chuàng)建
/*頭插法 創(chuàng)建鏈表*/
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 //新節(jié)點(diǎn)的next指向頭head
head = node//頭head換成新節(jié)點(diǎn)
}
return head
}
傳入 「1 2 3 4 5 6 7 8 9 10」
輸出 「10 9 8 7 6 5 4 3 2 1」
2. 尾插法創(chuàng)建
/*尾插法創(chuàng)建鏈表*/
func CreateNodeInsterOnTail(listData []int) *Node {
if len(listData) == 0 {
return &Node{data: 0}
}
head := &Node{data: listData[0]}
end := head //end 記錄鏈表的尾，不斷向end后插入新節(jié)點(diǎn)
for _, v := range listData[1:] {
end.next = &Node{data: v}
end = end.next //移動(dòng)end指針，指向新的尾節(jié)點(diǎn)
}
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. 逆序反轉(zhuǎn)鏈表
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 //當(dāng)前結(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)
if end == nil {
break
}
prev = cur //指針后移
cur = end //指針后移，處理下一個(gè)節(jié)點(diǎn)
end = end.next //temp作為中間節(jié)點(diǎn)进泼，記錄當(dāng)前結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的位置
}
head = cur
return head
}
4.2 遞歸
func ReverseNode2(head *Node) *Node {
if head == nil || head.next == nil {//遞歸的出口
return head
} else {
//一直遞歸城瞎，找到鏈表中最后一個(gè)節(jié)點(diǎn)
new_head := ReverseNode2(head.next)
//當(dāng)逐層退出時(shí)，new_head 的指向都不變惶桐，一直指向原鏈表中最后一個(gè)節(jié)點(diǎn)；
//遞歸每退出一層潘懊，函數(shù)中 head 指針的指向都會(huì)發(fā)生改變姚糊，都指向上一個(gè)節(jié)點(diǎn)。
//每退出一層授舟，都需要改變 head->next 節(jié)點(diǎn)指針域的指向救恨，同時(shí)令 head 所指節(jié)點(diǎn)的指針域?yàn)?NULL。
head.next.next = head
head.next = nil
//每一層遞歸結(jié)束释树，都要將新的頭指針返回給上一層肠槽。由此擎淤，即可保證整個(gè)遞歸過程中，能夠一直找得到新鏈表的表頭秸仙。
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 移動(dòng)至鏈表頭
end.next = head
head = end
//調(diào)整 end 的指向嘴拢，另其指向 beg 后的一個(gè)節(jié)點(diǎn)，為反轉(zhuǎn)下一個(gè)節(jié)點(diǎn)做準(zhǔn)備
end = beg.next
}
return head
}
5. 判斷鏈表中是否有環(huán)
快慢指針
/*
* 鏈表是否有環(huán)
* is 是否
* meet 有環(huán)是返回快慢指針的相遇節(jié)點(diǎn)
*/
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. 鏈表中環(huán)的入口點(diǎn)
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 //慢指針重新指向頭節(jié)點(diǎn)
for slow != fast {
slow = slow.next
fast = fast.next
}
return slow
}
相遇后寂纪，slow繼續(xù)一次移動(dòng)一個(gè)節(jié)點(diǎn)席吴，新另一node從鏈表頭開始一次移動(dòng)一個(gè)節(jié)點(diǎn)。
7. 鏈表中環(huán)的長度
//計(jì)算單鏈表環(huán)的長度
func ringLength(head *Node) int {
//首先通過上面的方法判斷弊攘，鏈表是否有環(huán)抢腐，并返回快慢指針的相遇點(diǎn)
is, meet := isRingLinkNode(head)
if is == false {
return 0 //沒有環(huán)，則直接返回
}
tmp := meet //tmp 停留在相遇點(diǎn)不再移動(dòng)
meet = meet.next
len := 1
for tmp != meet {
len++
meet = meet.next
}
return len
}
先用快慢指針相遇襟交，相遇后記錄相遇點(diǎn)迈倍，然后繼續(xù)next向下走并記錄走了幾步，
再次相遇時(shí)即環(huán)長度捣域。
8. 鏈表總長度
總長度 = 頭到入口點(diǎn)長度 + 環(huán)到長度
