golang实现单链表反转

单链表是一种常见的数据结构。对单链表反转的操作有以下几种方式:

  • 遍历缓存,再重组链表
  • 递归的方式
  • 单次遍历直接反转

下图演示了单次遍历直接反转的一步的操作过程,后续循环操作即可完成整个单链表的反转

reverse_ssl.png

golang代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main

import (
"fmt"
)

func () {
head := initList()
head = reverseList(head)
printList(head)
}

type node struct {
value interface{}
next *node
}

func initList() *node {
var list *node
var pre *node
for i := 0; i < 10; i++ {
tmp := &node{i + 1, nil}
if i == 0 {
list = tmp
pre = tmp
continue
}
pre.next = tmp
pre = tmp
}
return list
}

func printList(head *node) {
slice := make([]interface{}, 0, 10)
for cur := head; cur != nil; cur = cur.next {
slice = append(slice, cur.value)
}
fmt.Println(slice)
}

func reverseList(head *node) *node {
cur := head
if cur == nil {
return nil
}
next := cur.next
var pre *node

for {
if cur == nil {
break
}

cur.next = pre


pre = cur
cur = next
if next != nil {
next = next.next
}
}

return pre
}