• go语言｜数据结构：单链表（3）刷题实战

    目录

    单链表——刷题实战

    任意类型的数据域

    实例01

    快慢指针

    实例02

    反转链表

    实例03

    实例04

    交换节点

    实例05

    单链表——刷题实战

    任意类型的数据域

    之前的链表定义数据域都是整型int，如果需要不同类型的数据就要用到 interface{}。

    空接口 interface{}
    　　对于描述起不到任何的作用(因为它不包含任何的method），但interface{}在需要存储任意类型的数值的时候相当有用，因为它可以存储任意类型的数值。
    　　一个函数把interface{}作为参数，那么它可以接受任意类型的值作为参数；如果一个函数返回interface{}，那么也就可以返回任意类型的值，类似于C语言的void*类型。

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data interface{}
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	head *Node
    12. }
    13.  
    14. func (list *List) push(value interface{}) {
    15. 	node := &Node{data: value}
    16. 	p := list.head
    17. 	if p != nil {
    18. 		for p.next != nil {
    19. 			p = p.next
    20. 		}
    21. 		p.next = node
    22. 	} else {
    23. 		list.head = node
    24. 	}
    25. }
    26.  
    27. func (list *List) travel() {
    28. 	p := list.head
    29. 	for p != nil {
    30. 		fmt.Print(p.data)
    31. 		p = p.next
    32. 		if p != nil {
    33. 			fmt.Print("->")
    34. 		}
    35. 	}
    36. 	fmt.Println("")
    37. }
    38.  
    39. func main() {
    40.  
    41. 	node := new(List)
    42. 	node.push("abc")
    43. 	node.push(3.142)
    44. 	node.push('a')
    45. 	node.push(3 + 4i)
    46. 	node.push([]int{1, 2, 3})
    47. 	node.push([8]byte{'a', 3: 'd'})
    48. 	node.push(Node{1, &Node{2, nil}}.data)
    49. 	node.push(Node{1, &Node{2, nil}}.next)
    50. 	node.travel()
    51.  
    52. }
    53.  
    54. /*输出：
    55. abc->3.142->97->(3+4i)->[1 2 3]->[97 0 0 100 0 0 0 0]->1->&{2 }
    56. */

    实例01

    把字串中汉字除外的所有字符逐个存入链表，且数字以整型保存。 

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data interface{}
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	head *Node
    12. }
    13.  
    14. func (list *List) push(value interface{}) {
    15. 	node := &Node{data: value}
    16. 	p := list.head
    17. 	if p != nil {
    18. 		for p.next != nil {
    19. 			p = p.next
    20. 		}
    21. 		p.next = node
    22. 	} else {
    23. 		list.head = node
    24. 	}
    25. }
    26.  
    27. func (list *List) travel() {
    28. 	p := list.head
    29. 	for p != nil {
    30. 		fmt.Print(p.data)
    31. 		p = p.next
    32. 		if p != nil {
    33. 			fmt.Print("->")
    34. 		}
    35. 	}
    36. 	fmt.Println("")
    37. }
    38.  
    39. func main() {
    40.  
    41. 	node := new(List)
    42. 	str := "Golang数据结构123:单链表0789"
    43.  
    44. 	for _, s := range str {
    45. 		if s >= 48 && s < 58 {
    46. 			node.push(s - 48)
    47. 		} else if s < 128 {
    48. 			node.push(string(s))
    49. 		}
    50. 	}
    51. 	node.travel()
    52.  
    53. }
    54.  
    55. /*输出：
    56. G->o->l->a->n->g->1->2->3->:->0->7->8->9
    57. */

    快慢指针

    给单链表设置2个指针，其中一个指针先移动n个节点，然后同时移动这2个指针，那么当先移动的指针到达尾部时，后移动的那个指针就是倒数第 n 个节点。先移动的指针称“快指针”，后出发的指针称“慢指针”，其实一样“快”只是出发有先后。

    实例02

    删除链表中倒数第 n 个结点

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data interface{}
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	head *Node
    12. }
    13.  
    14. func (list *List) removNthBack(n int) {
    15. 	if n > list.size() {
    16. 		panic("range error: n <= List's size")
    17. 	}
    18. 	var fast, slow *Node
    19. 	head := list.head
    20. 	fast = head
    21. 	slow = head
    22. 	for i := 0; i < n; i++ {
    23. 		fast = fast.next
    24. 	}
    25. 	if fast == nil {
    26. 		list.head = head.next
    27. 		return
    28. 	}
    29. 	for fast.next != nil {
    30. 		fast = fast.next
    31. 		slow = slow.next
    32. 	}
    33. 	slow.next = slow.next.next
    34. }
    35.  
    36. func removNthBack(list *List, n int) *List {
    37. 	if n > list.size() {
    38. 		panic("range error: n <= List's size")
    39. 	}
    40. 	var fast, slow *Node
    41. 	head := list.head
    42. 	fast = head
    43. 	slow = head
    44. 	for i := 0; i < n; i++ {
    45. 		fast = fast.next
    46. 	}
    47. 	if fast == nil {
    48. 		list.head = head.next
    49. 		return list
    50. 	}
    51. 	for fast.next != nil {
    52. 		fast = fast.next
    53. 		slow = slow.next
    54. 	}
    55. 	slow.next = slow.next.next
    56. 	return list
    57. }
    58.  
    59. func (list *List) push(value interface{}) {
    60. 	node := &Node{data: value}
    61. 	p := list.head
    62. 	if p != nil {
    63. 		for p.next != nil {
    64. 			p = p.next
    65. 		}
    66. 		p.next = node
    67. 	} else {
    68. 		list.head = node
    69. 	}
    70. }
    71.  
    72. func (list *List) size() int {
    73. 	length := 0
    74. 	for p := list.head; p != nil; p = p.next {
    75. 		length++
    76. 	}
    77. 	return length
    78. }
    79.  
    80. func (list *List) travel() {
    81. 	p := list.head
    82. 	for p != nil {
    83. 		fmt.Print(p.data)
    84. 		p = p.next
    85. 		if p != nil {
    86. 			fmt.Print("->")
    87. 		}
    88. 	}
    89. 	fmt.Println("")
    90. }
    91.  
    92. func main() {
    93.  
    94. 	lst := new(List)
    95. 	str := "12309"
    96.  
    97. 	for _, s := range str {
    98. 		lst.push(s - 48)
    99. 	}
    100. 	lst.travel()
    101.  
    102. 	lst.removNthBack(3)
    103. 	lst.travel()
    104. 	lst = removNthBack(lst, 3)
    105. 	lst.travel()
    106. 	lst.removNthBack(2)
    107. 	lst.travel()
    108. 	//lst.removNthBack(10) //panic error
    109. 	lst.removNthBack(2)
    110. 	lst.travel()
    111. 	lst.removNthBack(1)
    112. 	lst.travel()
    113. 	//lst.removNthBack(1) //panic error
    114.  
    115. }
    116.  
    117. /*输出：
    118. 1->2->3->0->9
    119. 1->2->0->9
    120. 1->0->9
    121. 1->9
    122. 9
    124. */

    反转链表

    遍历一个链表，每个结点用头插法相接的新链表就是原链表的反转结果。

    实例03

    反转整个链表

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data interface{}
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	head *Node
    12. }
    13.  
    14. func (list *List) reverse() {
    15. 	res := &List{}
    16. 	for p := list.head; p != nil; p = p.next {
    17. 		node := &Node{p.data, nil}
    18. 		node.next = res.head
    19. 		res.head = node
    20. 	}
    21. 	list.head = res.head
    22. }
    23.  
    24. func (list *List) pushHead(value interface{}) {
    25. 	node := &Node{data: value}
    26. 	node.next = list.head
    27. 	list.head = node
    28. }
    29.  
    30. func (list *List) build(lst []interface{}) {
    31. 	for i := len(lst) - 1; i >= 0; i-- {
    32. 		node := &Node{data: lst[i]}
    33. 		node.next = list.head
    34. 		list.head = node
    35. 	}
    36. }
    37.  
    38. func (list *List) clear() {
    39. 	list.head = nil
    40. }
    41.  
    42. func (list *List) travel() {
    43. 	p := list.head
    44. 	for p != nil {
    45. 		fmt.Print(p.data)
    46. 		p = p.next
    47. 		if p != nil {
    48. 			fmt.Print("->")
    49. 		}
    50. 	}
    51. 	fmt.Println("")
    52. }
    53.  
    54. func main() {
    55.  
    56. 	lst := new(List)
    57.  
    58. 	for n := 5; n > 0; n-- {
    59. 		lst.pushHead(n)
    60. 	}
    61. 	lst.travel()
    62. 	lst.reverse()
    63. 	lst.travel()
    64.  
    65. 	lst.clear()
    66. 	lst.build([]interface{}{6.13, "/", 100000, "Hann", 1.0e-5})
    67. 	lst.travel()
    68. 	lst.reverse()
    69. 	lst.travel()
    70.  
    71. }
    72.  
    73. /*输出：
    74. 1->2->3->4->5
    75. 5->4->3->2->1
    76. 6.13->/->100000->Hann->1e-05
    77. 1e-05->Hann->100000->/->6.13
    78. */

    实例04

    反转链表的其中一段，反转从第m个结点到n个结点(其中0

    Input: 1->2->3->4->5->nil, m = 2, n = 4
    Output: 1->4->3->2->5->nil

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data interface{}
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	head *Node
    12. }
    13.  
    14. func reverseBetween(list *List, m int, n int) *List {
    15. 	list = list.Copy()
    16. 	head := list.head
    17. 	if head == nil || m >= n {
    18. 		return list
    19. 	}
    20. 	if m < 1 { //防止范围左端超限
    21. 		m = 1
    22. 	}
    23. 	node := &Node{0, head}
    24. 	p := node
    25. 	for i := 0; p.next != nil && i < m-1; i++ {
    26. 		p = p.next
    27. 	}
    28. 	if p.next == nil {
    29. 		return list
    30. 	}
    31. 	cur := p.next
    32. 	for i := 0; i < n-m && cur.next != nil; i++ {
    33. 		//由cur.next != nil防止范围右端超限
    34. 		tmp := p.next
    35. 		p.next = cur.next
    36. 		cur.next = cur.next.next
    37. 		p.next.next = tmp
    38. 	}
    39. 	list.head = node.next
    40. 	return list
    41. }
    42.  
    43. func (list *List) reverseBetween(m int, n int) {
    44. 	head := list.head
    45. 	if head == nil || m >= n {
    46. 		return
    47. 	}
    48. 	if m < 1 { //防止范围左端超限
    49. 		m = 1
    50. 	}
    51. 	node := &Node{0, head}
    52. 	p := node
    53. 	for i := 0; p.next != nil && i < m-1; i++ {
    54. 		p = p.next
    55. 	}
    56. 	if p.next == nil {
    57. 		return
    58. 	}
    59. 	cur := p.next
    60. 	for i := 0; i < n-m && cur.next != nil; i++ {
    61. 		//由cur.next != nil防止范围右端超限
    62. 		tmp := p.next
    63. 		p.next = cur.next
    64. 		cur.next = cur.next.next
    65. 		p.next.next = tmp
    66. 	}
    67. 	list.head = node.next
    68. }
    69.  
    70. func (list *List) pushHead(value interface{}) {
    71. 	node := &Node{data: value}
    72. 	node.next = list.head
    73. 	list.head = node
    74. }
    75.  
    76. func (list *List) build(lst []interface{}) {
    77. 	for i := len(lst) - 1; i >= 0; i-- {
    78. 		node := &Node{data: lst[i]}
    79. 		node.next = list.head
    80. 		list.head = node
    81. 	}
    82. }
    83.  
    84. func (list *List) Copy() *List {
    85. 	p := list.head
    86. 	res := &List{}
    87. 	if p != nil {
    88. 		node := &Node{p.data, nil}
    89. 		q := node
    90. 		for p = p.next; p != nil; p = p.next {
    91. 			q.next = &Node{p.data, nil}
    92. 			q = q.next
    93. 		}
    94. 		res.head = node
    95. 	}
    96. 	return res
    97. }
    98.  
    99. func (list *List) travel() {
    100. 	p := list.head
    101. 	for p != nil {
    102. 		fmt.Print(p.data)
    103. 		p = p.next
    104. 		if p != nil {
    105. 			fmt.Print("->")
    106. 		}
    107. 	}
    108. 	fmt.Println("")
    109. }
    110.  
    111. func main() {
    112.  
    113. 	list1 := new(List)
    114. 	list2 := new(List)
    115. 	for n := 5; n > 0; n-- {
    116. 		list1.pushHead(n)
    117. 	}
    118. 	list1.travel()
    119.  
    120. 	list2 = reverseBetween(list1, 2, 4)
    121. 	list2.travel()
    122. 	list2 = reverseBetween(list1, 2, 3)
    123. 	list2.travel()
    124. 	list2 = reverseBetween(list1, 2, 5)
    125. 	list2.travel()
    126. 	list2 = reverseBetween(list1, 2, 6)
    127. 	list2.travel()
    128. 	list2 = reverseBetween(list1, 1, 6)
    129. 	list2.travel()
    130. 	list2 = reverseBetween(list1, 0, 3)
    131. 	list2.travel()
    132. 	list1.reverseBetween(1, 3)
    133. 	list1.travel()
    134.  
    135. }
    136.  
    137. /*输出：
    138. 1->2->3->4->5
    139. 1->4->3->2->5
    140. 1->3->2->4->5
    141. 1->5->4->3->2
    142. 1->5->4->3->2
    143. 5->4->3->2->1
    144. 3->2->1->4->5
    145. 3->2->1->4->5
    146. */

    交换节点

    实例05

    链表的相邻节点两两交换位置

    Given 1->2->3->4, you should return the list as 2->1->4->3.

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data interface{}
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	head *Node
    12. }
    13.  
    14. func (list *List) swapPairs() {
    15. 	p := list.head
    16. 	if p == nil || p.next == nil {
    17. 		return
    18. 	}
    19. 	head := p.next
    20. 	var node, node2 *Node
    21. 	for p.next != nil {
    22. 		cur := p.next
    23. 		if node != nil && node.next != nil {
    24. 			node.next = cur
    25. 		}
    26. 		if p.next.next != nil {
    27. 			node2 = p.next.next
    28. 		}
    29. 		if p.next.next != nil {
    30. 			p.next = node2
    31. 		} else {
    32. 			p.next = nil
    33. 		}
    34. 		cur.next = p
    35. 		node = p
    36. 		if p.next != nil {
    37. 			p = node2
    38. 		}
    39. 	}
    40. 	list.head = head
    41. }
    42.  
    43. func swapPairs(list *List) *List {
    44. 	list = list.Copy()
    45. 	p := list.head
    46. 	if p == nil || p.next == nil {
    47. 		return list
    48. 	}
    49. 	head := p.next
    50. 	var node, node2 *Node
    51. 	for p.next != nil {
    52. 		cur := p.next
    53. 		if node != nil && node.next != nil {
    54. 			node.next = cur
    55. 		}
    56. 		if p.next.next != nil {
    57. 			node2 = p.next.next
    58. 		}
    59. 		if p.next.next != nil {
    60. 			p.next = node2
    61. 		} else {
    62. 			p.next = nil
    63. 		}
    64. 		cur.next = p
    65. 		node = p
    66. 		if p.next != nil {
    67. 			p = node2
    68. 		}
    69. 	}
    70. 	list.head = head
    71. 	return list
    72. }
    73.  
    74. func (list *List) Copy() *List {
    75. 	p := list.head
    76. 	res := &List{}
    77. 	if p != nil {
    78. 		node := &Node{p.data, nil}
    79. 		q := node
    80. 		for p = p.next; p != nil; p = p.next {
    81. 			q.next = &Node{p.data, nil}
    82. 			q = q.next
    83. 		}
    84. 		res.head = node
    85. 	}
    86. 	return res
    87. }
    88.  
    89. func (list *List) build(lst []interface{}) {
    90. 	for i := len(lst) - 1; i >= 0; i-- {
    91. 		node := &Node{data: lst[i]}
    92. 		node.next = list.head
    93. 		list.head = node
    94. 	}
    95. }
    96.  
    97. func (list *List) travel() {
    98. 	p := list.head
    99. 	for p != nil {
    100. 		fmt.Print(p.data)
    101. 		p = p.next
    102. 		if p != nil {
    103. 			fmt.Print("->")
    104. 		}
    105. 	}
    106. 	fmt.Println("")
    107. }
    108.  
    109. func main() {
    110.  
    111. 	list1 := new(List)
    112. 	list2 := new(List)
    113. 	list1.build([]interface{}{1, 2, 3, 4, 5, 6})
    114. 	list1.travel()
    115.  
    116. 	list2 = swapPairs(list1)
    117. 	list2.travel()
    118.  
    119. 	list2 = &List{&Node{0, nil}}
    120. 	list2.head.next = list1.Copy().head
    121. 	list2.travel()
    122. 	list2.swapPairs()
    123. 	list2.travel()
    124.  
    125. }
    126.  
    127. /*输出：
    128. 1->2->3->4->5->6
    129. 2->1->4->3->6->5
    130. 0->1->2->3->4->5->6
    131. 1->0->3->2->5->4->6
    132. */

     

  • 相关阅读:
    Dubbo线程池
    SpringBoot激活profiles的几种方式
    QImage
    α-SRHLA
    mysql的基本知识点
    Linux搭建zookeeper与kafka集群配置
    C语言程序设计笔记（浙大翁恺版） 第五周：循环控制
    Java实现简单图书操作系统思路讲解
    SQL查询优化---单表使用索引及常见索引失效优化
    DSP-FIR滤波器设计
  • 原文地址：https://blog.csdn.net/boysoft2002/article/details/126490925