• go语言｜数据结构：单链表（2）

    目录

    单向链表

    首元结点

    头结点

    头指针

    链表与节点

    插入单个元素

    数组插入链表

    链表长度

    链表副本

    链表拼接

    Cat()追加

    Add()左加

    节点删除

    删除首元结点

    删除尾结点

    习题解答

    单向链表

    　　又称单链表，单链表中每个结点包含两部分，分别是数据域和指针域，上一个结点的指针指向下一结点，依次相连，形成链表。三个概念：首元结点、头结点和头指针，其中头结点在链表中不是必须的。

    首元结点

    就是链表中存储第一个元素的结点。

    头结点

    是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以存储链表的长度或者其它的信息，也可以为空不存储任何信息。

    头指针

    是指向链表中第一个结点的指针。若链表中有头结点，则头指针指向头结点；若链表中没有头结点，则头指针指向首元结点。

    链表与节点

    引入单链表结构LinkList，仅保留头指针；与节点结构ListNode配合使用。头指针为空的单链表即为空链表，解决只使用节点结构不能构造空表的缺点。

    1. type ListNode struct {
    2. 	data int
    3. 	next *ListNode
    4. }
    5.  
    6. type LinkList struct {
    7. 	next *ListNode
    8. }

    插入单个元素

    头插法pushHead() 、 尾插法pushTail()

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type ListNode struct {
    6. 	data int
    7. 	next *ListNode
    8. }
    9.  
    10. type LinkList struct {
    11. 	next *ListNode
    12. }
    13.  
    14. func (head *LinkList) pushHead(value int) {
    15. 	node := &ListNode{data: value}
    16. 	node.next = head.next
    17. 	head.next = node
    18. }
    19.  
    20. func (head *LinkList) pushTail(value int) {
    21. 	node := &ListNode{data: value}
    22. 	p := head.next
    23. 	if p != nil {
    24. 		for p.next != nil {
    25. 			p = p.next
    26. 		}
    27. 		p.next = node
    28. 	} else {
    29. 		head.next = node
    30. 	}
    31. }
    32.  
    33. func (node *ListNode) travel() {
    34. 	for node != nil {
    35. 		fmt.Print(node.data)
    36. 		node = node.next
    37. 		if node != nil {
    38. 			fmt.Print("->")
    39. 		}
    40. 	}
    41. 	fmt.Println("")
    42. }
    43.  
    44. func (head *LinkList) travel() {
    45. 	head.next.travel()
    46. }
    47.  
    48. func main() {
    49.  
    50. 	nodes := &LinkList{}
    51. 	nodes.travel()
    52.  
    53. 	nodes.pushTail(1)
    54. 	nodes.travel()
    55. 	nodes.pushHead(2)
    56. 	nodes.pushHead(3)
    57. 	nodes.travel()
    58.  
    59. 	nodes.pushTail(4)
    60. 	nodes.pushTail(5)
    61. 	nodes.travel()
    62.  
    63. }
    64.  
    65. /*输出：
    67. 1
    68. 3->2->1
    69. 3->2->1->4->5
    70. */

    数组插入链表

    优化后插入多个元素：push()前插、append()追加

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

    链表长度

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data int
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	next *Node
    12. }
    13.  
    14. func Len(head *List) int {
    15. 	length := 0
    16. 	for p := head.next; p != nil; p = p.next {
    17. 		length++
    18. 	}
    19. 	return length
    20. }
    21.  
    22. func (head *List) size() int {
    23. 	return Len(head)
    24. }
    25.  
    26. func (head *List) build(list []int) {
    27. 	for i := len(list) - 1; i >= 0; i-- {
    28. 		node := &Node{data: list[i]}
    29. 		node.next = head.next
    30. 		head.next = node
    31. 	}
    32. }
    33.  
    34. func main() {
    35.  
    36. 	var node1, node2 *List
    37. 	node1 = new(List)
    38. 	node2 = new(List)
    39. 	fmt.Println(node1.size())
    40.  
    41. 	node1.build([]int{1, 2, 3, 5})
    42. 	node2.build([]int{7, 8, 9})
    43.  
    44. 	fmt.Println(node1.size())
    45. 	fmt.Println(Len(node2))
    46.  
    47. }
    48.  
    49. /*输出：
    50. 0
    51. 4
    52. 3
    53. */

    链表副本

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data int
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	next *Node
    12. }
    13.  
    14. func (head *List) Copy() *List {
    15. 	p := head.next
    16. 	list := &List{}
    17. 	node := &Node{p.data, nil}
    18. 	tail := node
    19. 	for p = p.next; p != nil; p = p.next {
    20. 		var linknode = Node{data: p.data}
    21. 		(*tail).next = &linknode
    22. 		tail = &linknode
    23. 	}
    24. 	list.next = node
    25. 	return list
    26. }
    27.  
    28. func (head *List) build(list []int) {
    29. 	for i := len(list) - 1; i >= 0; i-- {
    30. 		node := &Node{data: list[i]}
    31. 		node.next = head.next
    32. 		head.next = node
    33. 	}
    34. }
    35.  
    36. func (head *List) pushHead(value int) {
    37. 	node := &Node{data: value}
    38. 	node.next = head.next
    39. 	head.next = node
    40. }
    41.  
    42. func (head *List) travel() {
    43. 	p := head.next
    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. 	var node1, node2 *List
    57. 	node1 = new(List)
    58. 	node2 = new(List)
    59. 	node1.build([]int{1, 2, 3, 5})
    60. 	node2 = node1
    61.  
    62. 	node3 := node1.Copy() //保存副本
    63. 	node3.travel()
    64.  
    65. 	node1.pushHead(0)
    66. 	node1.travel()
    67. 	node2.travel()
    68. 	node3.travel() //保存的副本不随node1变化
    69.  
    70. }
    71.  
    72. /*输出：
    73. 1->2->3->5
    74. 0->1->2->3->5
    75. 0->1->2->3->5
    76. 1->2->3->5
    77. */

    链表拼接

    Cat()追加

    与尾插单个元素类似；另外拼接链表的副本有好处的，不信可把.Copy()去掉试试。

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data int
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	next *Node
    12. }
    13.  
    14. func (head *List) Cat(node *List) {
    15. 	p := head.next
    16. 	q := node.Copy() //使用副本，确保node不变
    17. 	if p != nil {
    18. 		for p.next != nil {
    19. 			p = p.next
    20. 		}
    21. 		p.next = q.next
    22. 	} else {
    23. 		head.next = q.next
    24. 	}
    25. }
    26.  
    27. func (head *List) Copy() *List {
    28. 	p := head.next
    29. 	list := &List{}
    30. 	node := &Node{p.data, nil}
    31. 	tail := node
    32. 	for p = p.next; p != nil; p = p.next {
    33. 		var linknode = Node{data: p.data}
    34. 		(*tail).next = &linknode
    35. 		tail = &linknode
    36. 	}
    37. 	list.next = node
    38. 	return list
    39. }
    40.  
    41. func (head *List) build(list []int) {
    42. 	for i := len(list) - 1; i >= 0; i-- {
    43. 		node := &Node{data: list[i]}
    44. 		node.next = head.next
    45. 		head.next = node
    46. 	}
    47. }
    48.  
    49. func (head *List) pushHead(value int) {
    50. 	node := &Node{data: value}
    51. 	node.next = head.next
    52. 	head.next = node
    53. }
    54.  
    55. func (head *List) pushTail(value int) {
    56. 	node := &Node{data: value}
    57. 	p := head.next
    58. 	if p != nil {
    59. 		for p.next != nil {
    60. 			p = p.next
    61. 		}
    62. 		p.next = node
    63. 	} else {
    64. 		head.next = node
    65. 	}
    66. }
    67.  
    68. func (head *List) travel() {
    69. 	p := head.next
    70. 	for p != nil {
    71. 		fmt.Print(p.data)
    72. 		p = p.next
    73. 		if p != nil {
    74. 			fmt.Print("->")
    75. 		}
    76. 	}
    77. 	fmt.Println("")
    78. }
    79.  
    80. func main() {
    81.  
    82. 	var node1, node2 *List
    83. 	node1 = new(List)
    84. 	node2 = new(List)
    85. 	node1.build([]int{1, 2, 3, 5})
    86. 	node2.build([]int{7, 8, 9})
    87.  
    88. 	node3 := &List{}
    89. 	node3.Cat(node1)
    90. 	node3.Cat(node2)
    91. 	node3.travel()
    92.  
    93. 	node1.travel()
    94. 	node2.travel()
    95.  
    96. }
    97.  
    98. /*输出：
    99. 1->2->3->5->7->8->9
    100. 1->2->3->5
    101. 7->8->9
    102. */

    Add()左加

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

    节点删除

    节点删除需要判断链表自身是否为空链表，判断条件增加 if head.next == nil || p.next == nil {...}

    删除首元结点

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

    删除尾结点

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data int
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	next *Node
    12. }
    13.  
    14. func (head *List) delTail() {
    15. 	p := head.next
    16. 	if head.next == nil || p.next == nil {
    17. 		head.next = nil
    18. 	} else {
    19. 		for p.next.next != nil {
    20. 			p = p.next
    21. 		}
    22. 		p.next = nil
    23. 	}
    24. }
    25.  
    26. func (head *List) build(list []int) {
    27. 	for i := len(list) - 1; i >= 0; i-- {
    28. 		node := &Node{data: list[i]}
    29. 		node.next = head.next
    30. 		head.next = node
    31. 	}
    32. }
    33.  
    34. func (head *List) travel() {
    35. 	for p := head.next; p != nil; p = p.next {
    36. 		fmt.Print(p.data)
    37. 		if p.next != nil {
    38. 			fmt.Print("->")
    39. 		}
    40. 	}
    41. 	fmt.Println("")
    42. }
    43.  
    44. func main() {
    45.  
    46. 	nodes := &List{}
    47.  
    48. 	nodes.build([]int{1, 2, 3})
    49. 	nodes.travel()
    50. 	nodes.delTail()
    51. 	nodes.travel()
    52. 	nodes.delTail()
    53. 	nodes.travel()
    54. 	nodes.delTail()
    55. 	nodes.travel()
    56. 	nodes.delTail()
    57. 	nodes.travel()
    58.  
    59. }
    60.  
    61. /*输出：
    62. 1->2->3
    63. 1->2
    64. 1
    67. */

    习题解答

    1. 给定一个已排序链表，删除重复节点，原始链表中多次出现的数字只能保留一次。

    示例1

    输入: 1->1->2
    输出: 1->2

    示例2

    输入: 1->1->2->3->3
    输出: 1->2->3

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data int
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	next *Node
    12. }
    13.  
    14. func (head *List) removeDuplicates() {
    15. 	p := head.next
    16. 	node := &List{}
    17. 	data := p.data
    18. 	node.pushTail(data)
    19. 	for p != nil {
    20. 		if p.data != data {
    21. 			data = p.data
    22. 			node.pushTail(data)
    23. 		}
    24. 		p = p.next
    25. 	}
    26. 	head.next = node.next
    27. }
    28.  
    29. func (head *List) pushTail(value int) {
    30. 	node := &Node{data: value}
    31. 	p := head.next
    32. 	if p != nil {
    33. 		for p.next != nil {
    34. 			p = p.next
    35. 		}
    36. 		p.next = node
    37. 	} else {
    38. 		head.next = node
    39. 	}
    40. }
    41.  
    42. func (head *List) build(list []int) {
    43. 	for i := len(list) - 1; i >= 0; i-- {
    44. 		node := &Node{data: list[i]}
    45. 		node.next = head.next
    46. 		head.next = node
    47. 	}
    48. }
    49.  
    50. func (head *List) clear() {
    51. 	head.next = nil
    52. }
    53.  
    54. func (head *List) travel() {
    55. 	for p := head.next; p != nil; p = p.next {
    56. 		fmt.Print(p.data)
    57. 		if p.next != nil {
    58. 			fmt.Print("->")
    59. 		}
    60. 	}
    61. 	fmt.Println()
    62. 	//fmt.Println("")
    63. }
    64.  
    65. func main() {
    66.  
    67. 	nodes := &List{}
    68.  
    69. 	nodes.build([]int{1, 1, 2})
    70. 	nodes.travel()
    71. 	nodes.removeDuplicates()
    72. 	nodes.travel()
    73.  
    74. 	nodes.clear()
    75. 	nodes.build([]int{1, 1, 2, 3, 3})
    76. 	nodes.travel()
    77. 	nodes.removeDuplicates()
    78. 	nodes.travel()
    79.  
    80. 	nodes.clear()
    81. 	nodes.build([]int{1, 2, 3, 3, 4, 4, 5})
    82. 	nodes.travel()
    83. 	nodes.removeDuplicates()
    84. 	nodes.travel()
    85.  
    86. 	nodes.clear()
    87. 	nodes.build([]int{1, 1, 1, 2, 3, 3, 3})
    88. 	nodes.travel()
    89. 	nodes.removeDuplicates()
    90. 	nodes.travel()
    91.  
    92. }
    93.  
    94. /*输出：
    95. 1->1->2
    96. 1->2
    97. 1->1->2->3->3
    98. 1->2->3
    99. 1->2->3->3->4->4->5
    100. 1->2->3->4->5
    101. 1->1->1->2->3->3->3
    102. 1->2->3
    103. */

    2. 给定一个排序链表，删除所有重复的节点，留原始链表有过重复的数字一个也不留。

    示例1

    输入: 1->2->3->3->4->4->5
    输出: 1->2->5

    示例2

    输入: 1->1->1->2->3
    输出: 2->3

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data int
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	next *Node
    12. }
    13.  
    14. func (head *List) deleteDuplicates() {
    15. 	p := head.next
    16. 	node := &List{}
    17. 	if p.next == nil || p.data != p.next.data {
    18. 		node.pushTail(p.data)
    19. 	}
    20. 	if p.next != nil {
    21. 		data := p.data
    22. 		for p.next.next != nil {
    23. 			data = p.data
    24. 			p = p.next
    25. 			if data != p.data && p.data != p.next.data {
    26. 				node.pushTail(p.data)
    27. 			}
    28. 		}
    29. 		if p.data != p.next.data {
    30. 			node.pushTail(p.next.data)
    31. 		}
    32. 	}
    33. 	head.next = node.next
    34. }
    35.  
    36. func (head *List) pushTail(value int) {
    37. 	node := &Node{data: value}
    38. 	p := head.next
    39. 	if p != nil {
    40. 		for p.next != nil {
    41. 			p = p.next
    42. 		}
    43. 		p.next = node
    44. 	} else {
    45. 		head.next = node
    46. 	}
    47. }
    48.  
    49. func (head *List) build(list []int) {
    50. 	for i := len(list) - 1; i >= 0; i-- {
    51. 		node := &Node{data: list[i]}
    52. 		node.next = head.next
    53. 		head.next = node
    54. 	}
    55. }
    56.  
    57. func (head *List) clear() {
    58. 	head.next = nil
    59. }
    60.  
    61. func (head *List) travel() {
    62. 	for p := head.next; p != nil; p = p.next {
    63. 		fmt.Print(p.data)
    64. 		if p.next != nil {
    65. 			fmt.Print("->")
    66. 		}
    67. 	}
    68. 	fmt.Println("")
    69. 	//fmt.Println("")
    70. }
    71.  
    72. func main() {
    73.  
    74. 	nodes := &List{}
    75.  
    76. 	nodes.build([]int{1, 1, 1, 2, 3})
    77. 	nodes.travel()
    78. 	nodes.deleteDuplicates()
    79. 	nodes.travel()
    80.  
    81. 	nodes.clear()
    82. 	nodes.build([]int{1, 2, 3, 3, 4, 4, 5})
    83. 	nodes.travel()
    84. 	nodes.deleteDuplicates()
    85. 	nodes.travel()
    86.  
    87. 	nodes.clear()
    88. 	nodes.build([]int{1, 1, 2, 3, 3, 4, 5})
    89. 	nodes.travel()
    90. 	nodes.deleteDuplicates()
    91. 	nodes.travel()
    92.  
    93. 	nodes.clear()
    94. 	nodes.build([]int{1, 2, 3, 3, 4, 5, 5})
    95. 	nodes.travel()
    96. 	nodes.deleteDuplicates()
    97. 	nodes.travel()
    98.  
    99. }
    100.  
    101. /*输出：
    102. 1->1->1->2->3
    103. 2->3
    104. 1->2->3->3->4->4->5
    105. 1->2->5
    106. 1->1->2->3->3->4->5
    107. 2->4->5
    108. 1->2->3->3->4->5->5
    109. 1->2->4
    110. */

    3. 给定两个有序链表(升序)，合并为一个新的有序链表并返回。

    示例1

    输入：1->2>4->8
    　　　1->3->3->5->5
    输出：1->1->2->3->3->4->5->5->8

    示例2

    输入：0->2>4->8
    　　　1->3->5->7->9
    输出：0->1->2->3->4->5->6->7->8->9

    1、递归法：

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data int
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	head *Node
    12. }
    13.  
    14. //递归法合并有序链表
    15. func recurMerge(p1 *Node, p2 *Node) *Node {
    16. 	if p1 == nil {
    17. 		return p2
    18. 	}
    19. 	if p2 == nil {
    20. 		return p1
    21. 	}
    22. 	p := new(Node)
    23. 	if p1.data < p2.data {
    24. 		p = p1
    25. 		p.next = recurMerge(p1.next, p2)
    26. 	} else {
    27. 		p = p2
    28. 		p.next = recurMerge(p1, p2.next)
    29. 	}
    30. 	return p
    31. }
    32.  
    33. func (list *List) build(lst []int) {
    34. 	for i := len(lst) - 1; i >= 0; i-- {
    35. 		node := &Node{data: lst[i]}
    36. 		node.next = list.head
    37. 		list.head = node
    38. 	}
    39. }
    40.  
    41. func (list *List) Copy() *List {
    42. 	p := list.head
    43. 	res := &List{}
    44. 	if p != nil {
    45. 		node := &Node{p.data, nil}
    46. 		q := node
    47. 		for p = p.next; p != nil; p = p.next {
    48. 			q.next = &Node{p.data, nil}
    49. 			q = q.next
    50. 		}
    51. 		res.head = node
    52. 	}
    53. 	return res
    54. }
    55.  
    56. func (list *List) travel() {
    57. 	for p := list.head; p != nil; p = p.next {
    58. 		fmt.Print(p.data)
    59. 		if p.next != nil {
    60. 			fmt.Print("->")
    61. 		}
    62. 	}
    63. 	fmt.Println("")
    64. }
    65.  
    66. func main() {
    67.  
    68. 	List1 := &List{}
    69. 	List2 := &List{}
    70. 	List1.build([]int{1, 2, 4, 8})
    71. 	List2.build([]int{1, 3, 3, 5, 5})
    72. 	node1 := List1.Copy().head
    73. 	node2 := List2.Copy().head
    74.  
    75. 	List0 := &List{}
    76. 	List0.head = recurMerge(node1, node2)
    77. 	List0.travel()
    78. 	List1.travel()
    79. 	List2.travel()
    80.  
    81. 	//不使用副本的对比
    82. 	node1 = List1.head
    83. 	node2 = List2.head
    84.  
    85. 	List0 = &List{}
    86. 	List0.head = recurMerge(node1, node2)
    87. 	List0.travel()
    88. 	List1.travel()
    89. 	List2.travel()
    90.  
    91. 	//另一组合并
    92. 	List1 = &List{}
    93. 	List2 = &List{}
    94. 	List1.build([]int{0, 2, 4, 8})
    95. 	List2.build([]int{1, 3, 5, 7, 9})
    96. 	node1 = List1.Copy().head
    97. 	node2 = List2.Copy().head
    98.  
    99. 	List0 = &List{}
    100. 	List0.head = recurMerge(node1, node2)
    101. 	List0.travel()
    102. 	List1.travel()
    103. 	List2.travel()
    104.  
    105. }
    106.  
    107. /*输出：
    108. 1->1->2->3->3->4->5->5->8
    109. 1->2->4->8
    110. 1->3->3->5->5
    111. 1->1->2->3->3->4->5->5->8
    112. 1->2->3->3->4->5->5->8
    113. 1->1->2->3->3->4->5->5->8
    114. 0->1->2->3->4->5->7->8->9
    115. 0->2->4->8
    116. 1->3->5->7->9
    117. */

    本例中链表类的next指针改名为head：

    type List struct {
        head *Node
    } 

    2、常规遍历：

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type Node struct {
    6. 	data int
    7. 	next *Node
    8. }
    9.  
    10. type List struct {
    11. 	head *Node
    12. }
    13.  
    14. func mergeLists(list1 *List, list2 *List) *List {
    15. 	list := &List{&Node{}} //初始赋值时多余一个默认值0
    16. 	p := list.head
    17. 	p1 := list1.Copy().head  //使用副本保留链表原样
    18. 	p2 := list2.Copy().head
    19. 	for ; p1 != nil && p2 != nil; p = p.next {
    20. 		if p1.data < p2.data {
    21. 			p.next = p1
    22. 			p1 = p1.next
    23. 		} else {
    24. 			p.next = p2
    25. 			p2 = p2.next
    26. 		}
    27. 	}
    28. 	if p1 == nil {
    29. 		p.next = p2
    30. 	} else if p2 == nil {
    31. 		p.next = p1
    32. 	}
    33. 	list.head = list.head.next //去掉初始化时的0值
    34. 	return list
    35. }
    36.  
    37. func (list *List) build(lst []int) {
    38. 	for i := len(lst) - 1; i >= 0; i-- {
    39. 		node := &Node{data: lst[i]}
    40. 		node.next = list.head
    41. 		list.head = node
    42. 	}
    43. }
    44.  
    45. func (list *List) Copy() *List {
    46. 	p := list.head
    47. 	res := &List{}
    48. 	if p != nil {
    49. 		node := &Node{p.data, nil}
    50. 		q := node
    51. 		for p = p.next; p != nil; p = p.next {
    52. 			q.next = &Node{p.data, nil}
    53. 			q = q.next
    54. 		}
    55. 		res.head = node
    56. 	}
    57. 	return res
    58. }
    59.  
    60. func (list *List) travel() {
    61. 	for p := list.head; p != nil; p = p.next {
    62. 		fmt.Print(p.data)
    63. 		if p.next != nil {
    64. 			fmt.Print("->")
    65. 		}
    66. 	}
    67. 	fmt.Println("")
    68. }
    69.  
    70. func main() {
    71.  
    72. 	List1 := &List{}
    73. 	List2 := &List{}
    74. 	List1.build([]int{1, 2, 4, 8})
    75. 	List2.build([]int{1, 3, 3, 5, 5})
    76.  
    77. 	List0 := mergeLists(List1, List2)
    78. 	List0.travel()
    79. 	List1.travel()
    80. 	List2.travel()
    81.  
    82. 	List1 = &List{}
    83. 	List2 = &List{}
    84. 	List1.build([]int{0, 2, 4, 8})
    85. 	List2.build([]int{1, 3, 5, 7, 9})
    86.  
    87. 	List0 = mergeLists(List1, List2)
    88. 	List0.travel()
    89. 	List1.travel()
    90. 	List2.travel()
    91.  
    92. }
    93.  
    94. /*输出：
    95. 1->1->2->3->3->4->5->5->8
    96. 1->2->4->8
    97. 1->3->3->5->5
    98. 0->1->2->3->4->5->7->8->9
    99. 0->2->4->8
    100. 1->3->5->7->9
    101. */

  • 相关阅读:
    JavaWeb、终章案例
    KeyDB源码解析二——线程安全
    WEB前端网页设计 HTML CSS 网页设计参数 - 【盒子模型】
    谷粒商城 高级篇 (十七) --------- 单点登录
    PyTorch深度学习基础之Tensor对象及其应用的讲解及实战（附源码 简单易懂 包括分段 映射 矩阵乘法 随机数等等）
    一篇文章带你搞定Java封装
    HBase 常见问题总结（一）
    LM小型可编程控制器软件（基于CoDeSys）笔记十七：pto脉冲功能块
    gazebo中vins-fusion在仿真小车上的部署
    初识C语言
  • 原文地址：https://blog.csdn.net/boysoft2002/article/details/126450718