devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：weixin_40725706 | 2024-04-14 12:19:51

赞

踩

go 单链表遍历

目录

单链表——刷题实战

任意类型的数据域

实例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("<nil>")
  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 <nil>}<nil>
  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("<nil>")
  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<nil>
  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("<nil>")
  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<nil>
  119. 1->2->0->9<nil>
  120. 1->0->9<nil>
  121. 1->9<nil>
  122. 9<nil>
  123. <nil>
  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("<nil>")
  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<nil>
  75. 5->4->3->2->1<nil>
  76. 6.13->/->100000->Hann->1e-05<nil>
  77. 1e-05->Hann->100000->/->6.13<nil>
  78. */

实例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. 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("<nil>")
  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<nil>
  139. 1->4->3->2->5<nil>
  140. 1->3->2->4->5<nil>
  141. 1->5->4->3->2<nil>
  142. 1->5->4->3->2<nil>
  143. 5->4->3->2->1<nil>
  144. 3->2->1->4->5<nil>
  145. 3->2->1->4->5<nil>
  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("<nil>")
  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<nil>
  129. 2->1->4->3->6->5<nil>
  130. 0->1->2->3->4->5->6<nil>
  131. 1->0->3->2->5->4->6<nil>
  132. */

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/422112
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号