logo头像

待到风起时,扬帆济沧海

单向链表

本文于419天之前发表,文中内容可能已经过时。

操作流程示意图

1183379-529d87f81914f457.jpg

完整代码

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

type Node struct {
Data int
Next *Node
}

type SingleLinkedList struct {
head *Node
}

func (this *SingleLinkedList) SingleLinkedList() {
this.head = nil
}

func (this *SingleLinkedList) SetHead(head *Node) {
this.head = head
}
func (this *SingleLinkedList) GetHead() *Node {
return this.head
}

func (this *SingleLinkedList) IsEmpty() bool {
return this.head == nil
}

/**
获取链表长度
*/
func (this *SingleLinkedList) Length() int {
currentNode := this.head
length := 0
for currentNode != nil {
length++
currentNode = currentNode.Next

}
return length
}

/**
清空链表
*/
func (this *SingleLinkedList) Clean() {
this.head = nil
}

/**
获取数据
*/
func (this *SingleLinkedList) Get(i int) int {
currentNode := this.head //当前节点指向首节点
j := 0
for currentNode != nil && j < i {
j++
currentNode = currentNode.Next

}
if i < 0 || currentNode == nil {
panic(fmt.Sprintf("第%d个元素不存在", i))
}
return currentNode.Data
}

/**
头部插入
*/
func (this *SingleLinkedList) AddHead(data int) {
node := &Node{Data: data, Next: nil}
node.Next = this.head
this.head = node
}

/**
头部删除
*/
func (this *SingleLinkedList) DelHead() {
this.head = this.head.Next
}

/**
从尾部追加
*/
func (this *SingleLinkedList) Append(data int) {
node := &Node{Data: data, Next: nil}
currentNode := this.head //当前节点指向首节点
for currentNode.Next != nil {
currentNode = currentNode.Next
}
currentNode.Next = node
}

/**
打印数据
*/
func (this *SingleLinkedList) Display() {
head := this.head
sb := &strings.Builder{}
sb.WriteString("[")
for head != nil {
sb.WriteString(strconv.Itoa(head.Data) + "->")
head = head.Next
}
sb.WriteString("]")
fmt.Println(sb.String())
}

func (this *SingleLinkedList) insert(i int, data int) {
if i < 0 {
this.AddHead(data)
} else if i > this.Length() {
this.Append(data)
} else {
pre := this.head
count := 0
for count < i {
pre = pre.Next
count++
}
node := &Node{Data: data}
node.Next = pre.Next
pre.Next = node

}
}

/**
移除数据
*/
func (this *SingleLinkedList) remove(data int) {
curr := this.head
if curr.Data == data {
this.head = curr.Next
} else {
for curr.Next != nil {
if curr.Next.Data == data {
curr.Next = curr.Next.Next
} else {
curr = curr.Next
}
}
}

递归法-反转

递归反转法:在反转当前节点之前先反转后续节点。这样从头结点开始,层层深入直到尾结点才开始反转指针域的指向。简单的说就是从尾结点开始,逆向反转各个结点的指针域指向,其过程图如下所示:

  • head:是前一结点的指针域(PS:前一结点的指针域指向当前结点)
  • head.getNext():是当前结点的指针域(PS:当前结点的指针域指向下一结点)
  • reHead:是反转后新链表的头结点(即原来单链表的尾结点)

2.jpg

1
2
3
4
5
6
7
8
9
10
func (this *SingleLinkedList) reverse(head *Node) *Node {
if head == nil || head.Next == nil {
return head
}
next := head.Next
new_head := this.reverse(next)
next.Next = head
head.Next = nil
return new_head
}

结果

1
2
3
4
5
6
newHead := l.reverse(l.GetHead())
l.SetHead(newHead)
l.Display()
//output
[69->3->97->171->118->122->]
[122->118->171->97->3->69->]

遍历法-反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (this *SingleLinkedList) reverse2(head *Node) *Node {
if head == nil || head.Next == nil {
return head
}
var pre *Node //前一节点
cur := head //当前节点
var next *Node // 下一结点

for cur != nil { // 当前结点为null,说明位于尾结点
next = cur.Next //nextNode 指向下一个节点
cur.Next = pre //将当前节点next域指向前一个节点
pre = cur //preNode 指针向后移动
cur = next //curNode指针向后移动

}
return pre
}

评论系统未开启,无法评论!