任意类型的数据域
之前的链表定义数据域都是整型int,如果需要不同类型的数据就要用到 interface{}。
空接口 interface{}
对于描述起不到任何的作用(因为它不包含任何的method),但interface{}在需要存储任意类型的数值的时候相当有用,因为它可以存储任意类型的数值。
一个函数把interface{}作为参数,那么它可以接受任意类型的值作为参数;如果一个函数返回interface{},那么也就可以返回任意类型的值,类似于C语言的void*类型。
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
|
package main import "fmt" type Node struct { data interface {} next *Node } type List struct { head *Node } func (list *List) push(value interface {}) { node := &Node{data: value} p := list.head if p != nil { for p.next != nil { p = p.next } p.next = node } else { list.head = node } } func (list *List) travel() { p := list.head for p != nil { fmt. Print (p.data) p = p.next if p != nil { fmt. Print ( "->" ) } } fmt. Println ( "<nil>" ) } func main() { node := new (List) node.push( "abc" ) node.push( 3.142 ) node.push( 'a' ) node.push( 3 + 4i) node.push([] int { 1 , 2 , 3 }) node.push([ 8 ] byte { 'a' , 3 : 'd' }) node.push(Node{ 1 , &Node{ 2 , nil }}.data) node.push(Node{ 1 , &Node{ 2 , nil }}.next) node.travel() } /*输出: abc->3.142->97->(3+4i)->[1 2 3]->[97 0 0 100 0 0 0 0]->1->&{2 <nil>}<nil> */ |
实例01
把字串中汉字除外的所有字符逐个存入链表,且数字以整型保存。
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
|
package main import "fmt" type Node struct { data interface {} next *Node } type List struct { head *Node } func (list *List) push(value interface {}) { node := &Node{data: value} p := list.head if p != nil { for p.next != nil { p = p.next } p.next = node } else { list.head = node } } func (list *List) travel() { p := list.head for p != nil { fmt. Print (p.data) p = p.next if p != nil { fmt. Print ( "->" ) } } fmt. Println ( "<nil>" ) } func main() { node := new (List) str := "Golang数据结构123:单链表0789" for _, s := range str { if s >= 48 && s < 58 { node.push(s - 48 ) } else if s < 128 { node.push( string (s)) } } node.travel() } /*输出: G->o->l->a->n->g->1->2->3->:->0->7->8->9<nil> */ |
快慢指针
给单链表设置2个指针,其中一个指针先移动n个节点,然后同时移动这2个指针,那么当先移动的指针到达尾部时,后移动的那个指针就是倒数第 n 个节点。先移动的指针称“快指针”,后出发的指针称“慢指针”,其实一样“快”只是出发有先后。
实例02
删除链表中倒数第 n 个结点
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
|
package main import "fmt" type Node struct { data interface {} next *Node } type List struct { head *Node } func (list *List) removNthBack(n int ) { if n > list.size() { panic ( "range error: n <= List's size" ) } var fast, slow *Node head := list.head fast = head slow = head for i := 0 ; i < n; i++ { fast = fast.next } if fast == nil { list.head = head.next return } for fast.next != nil { fast = fast.next slow = slow.next } slow.next = slow.next.next } func removNthBack(list *List, n int ) *List { if n > list.size() { panic ( "range error: n <= List's size" ) } var fast, slow *Node head := list.head fast = head slow = head for i := 0 ; i < n; i++ { fast = fast.next } if fast == nil { list.head = head.next return list } for fast.next != nil { fast = fast.next slow = slow.next } slow.next = slow.next.next return list } func (list *List) push(value interface {}) { node := &Node{data: value} p := list.head if p != nil { for p.next != nil { p = p.next } p.next = node } else { list.head = node } } func (list *List) size() int { length := 0 for p := list.head; p != nil ; p = p.next { length++ } return length } func (list *List) travel() { p := list.head for p != nil { fmt. Print (p.data) p = p.next if p != nil { fmt. Print ( "->" ) } } fmt. Println ( "<nil>" ) } func main() { lst := new (List) str := "12309" for _, s := range str { lst.push(s - 48 ) } lst.travel() lst.removNthBack( 3 ) lst.travel() lst = removNthBack(lst, 3 ) lst.travel() lst.removNthBack( 2 ) lst.travel() //lst.removNthBack(10) //panic error lst.removNthBack( 2 ) lst.travel() lst.removNthBack( 1 ) lst.travel() //lst.removNthBack(1) //panic error } /*输出: 1->2->3->0->9<nil> 1->2->0->9<nil> 1->0->9<nil> 1->9<nil> 9<nil> <nil> */ |
反转链表
遍历一个链表,每个结点用头插法相接的新链表就是原链表的反转结果。
实例03
反转整个链表
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
|
package main import "fmt" type Node struct { data interface {} next *Node } type List struct { head *Node } func (list *List) reverse() { res := &List{} for p := list.head; p != nil ; p = p.next { node := &Node{p.data, nil } node.next = res.head res.head = node } list.head = res.head } func (list *List) pushHead(value interface {}) { node := &Node{data: value} node.next = list.head list.head = node } func (list *List) build(lst [] interface {}) { for i := len (lst) - 1 ; i >= 0 ; i-- { node := &Node{data: lst[i]} node.next = list.head list.head = node } } func (list *List) clear() { list.head = nil } func (list *List) travel() { p := list.head for p != nil { fmt. Print (p.data) p = p.next if p != nil { fmt. Print ( "->" ) } } fmt. Println ( "<nil>" ) } func main() { lst := new (List) for n := 5 ; n > 0 ; n-- { lst.pushHead(n) } lst.travel() lst.reverse() lst.travel() lst.clear() lst.build([] interface {}{ 6.13 , "/" , 100000 , "Hann" , 1 .0e- 5 }) lst.travel() lst.reverse() lst.travel() } /*输出: 1->2->3->4->5<nil> 5->4->3->2->1<nil> 6.13->/->100000->Hann->1e-05<nil> 1e-05->Hann->100000->/->6.13<nil> */ |
实例04
反转链表的其中一段,反转从第m个结点到n个结点(其中0<m<=n<=length of List)
Input: 1->2->3->4->5->nil, m = 2, n = 4
Output: 1->4->3->2->5->nil
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
142
143
144
145
146
|
package main import "fmt" type Node struct { data interface {} next *Node } type List struct { head *Node } func reverseBetween(list *List, m int , n int ) *List { list = list. Copy () head := list.head if head == nil || m >= n { return list } if m < 1 { //防止范围左端超限 m = 1 } node := &Node{ 0 , head} p := node for i := 0 ; p.next != nil && i < m- 1 ; i++ { p = p.next } if p.next == nil { return list } cur := p.next for i := 0 ; i < n-m && cur.next != nil ; i++ { //由cur.next != nil防止范围右端超限 tmp := p.next p.next = cur.next cur.next = cur.next.next p.next.next = tmp } list.head = node.next return list } func (list *List) reverseBetween(m int , n int ) { head := list.head if head == nil || m >= n { return } if m < 1 { //防止范围左端超限 m = 1 } node := &Node{ 0 , head} p := node for i := 0 ; p.next != nil && i < m- 1 ; i++ { p = p.next } if p.next == nil { return } cur := p.next for i := 0 ; i < n-m && cur.next != nil ; i++ { //由cur.next != nil防止范围右端超限 tmp := p.next p.next = cur.next cur.next = cur.next.next p.next.next = tmp } list.head = node.next } func (list *List) pushHead(value interface {}) { node := &Node{data: value} node.next = list.head list.head = node } func (list *List) build(lst [] interface {}) { for i := len (lst) - 1 ; i >= 0 ; i-- { node := &Node{data: lst[i]} node.next = list.head list.head = node } } func (list *List) Copy () *List { p := list.head res := &List{} if p != nil { node := &Node{p.data, nil } q := node for p = p.next; p != nil ; p = p.next { q.next = &Node{p.data, nil } q = q.next } res.head = node } return res } func (list *List) travel() { p := list.head for p != nil { fmt. Print (p.data) p = p.next if p != nil { fmt. Print ( "->" ) } } fmt. Println ( "<nil>" ) } func main() { list1 := new (List) list2 := new (List) for n := 5 ; n > 0 ; n-- { list1.pushHead(n) } list1.travel() list2 = reverseBetween(list1, 2 , 4 ) list2.travel() list2 = reverseBetween(list1, 2 , 3 ) list2.travel() list2 = reverseBetween(list1, 2 , 5 ) list2.travel() list2 = reverseBetween(list1, 2 , 6 ) list2.travel() list2 = reverseBetween(list1, 1 , 6 ) list2.travel() list2 = reverseBetween(list1, 0 , 3 ) list2.travel() list1.reverseBetween( 1 , 3 ) list1.travel() } /*输出: 1->2->3->4->5<nil> 1->4->3->2->5<nil> 1->3->2->4->5<nil> 1->5->4->3->2<nil> 1->5->4->3->2<nil> 5->4->3->2->1<nil> 3->2->1->4->5<nil> 3->2->1->4->5<nil> */ |
交换节点
实例05
链表的相邻节点两两交换位置
Given 1->2->3->4, you should return the list as 2->1->4->3.
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
|
package main import "fmt" type Node struct { data interface {} next *Node } type List struct { head *Node } func (list *List) swapPairs() { p := list.head if p == nil || p.next == nil { return } head := p.next var node, node2 *Node for p.next != nil { cur := p.next if node != nil && node.next != nil { node.next = cur } if p.next.next != nil { node2 = p.next.next } if p.next.next != nil { p.next = node2 } else { p.next = nil } cur.next = p node = p if p.next != nil { p = node2 } } list.head = head } func swapPairs(list *List) *List { list = list. Copy () p := list.head if p == nil || p.next == nil { return list } head := p.next var node, node2 *Node for p.next != nil { cur := p.next if node != nil && node.next != nil { node.next = cur } if p.next.next != nil { node2 = p.next.next } if p.next.next != nil { p.next = node2 } else { p.next = nil } cur.next = p node = p if p.next != nil { p = node2 } } list.head = head return list } func (list *List) Copy () *List { p := list.head res := &List{} if p != nil { node := &Node{p.data, nil } q := node for p = p.next; p != nil ; p = p.next { q.next = &Node{p.data, nil } q = q.next } res.head = node } return res } func (list *List) build(lst [] interface {}) { for i := len (lst) - 1 ; i >= 0 ; i-- { node := &Node{data: lst[i]} node.next = list.head list.head = node } } func (list *List) travel() { p := list.head for p != nil { fmt. Print (p.data) p = p.next if p != nil { fmt. Print ( "->" ) } } fmt. Println ( "<nil>" ) } func main() { list1 := new (List) list2 := new (List) list1.build([] interface {}{ 1 , 2 , 3 , 4 , 5 , 6 }) list1.travel() list2 = swapPairs(list1) list2.travel() list2 = &List{&Node{ 0 , nil }} list2.head.next = list1. Copy ().head list2.travel() list2.swapPairs() list2.travel() } /*输出: 1->2->3->4->5->6<nil> 2->1->4->3->6->5<nil> 0->1->2->3->4->5->6<nil> 1->0->3->2->5->4->6<nil> */ |
以上就是Go语言数据结构之单链表的实例详解的详细内容,更多关于Go语言单链表的资料请关注服务器之家其它相关文章!
原文链接:https://blog.csdn.net/boysoft2002/article/details/126490925