关于数组和链表的几个必知必会的代码实现
数组
实现一个支持动态扩容的数组实现一个大小固定的有序数组，支持动态增删改操作实现两个有序数组合并为一个有序数组
链表
实现单链表、循环链表、双向链表，支持增删操作单链表反转链表中的环检测两个有序链表的合并为一个有序链表删除链表倒数第n个结点求链表的中间结点
1. 实现两个有序数组合并为一个有序数组代码：
package main
import "fmt"
//实现一个支持动态扩容的数组
//实现一个大小固定的有序数组，支持动态增删改操作
//实现两个有序数组合并为一个有序数组
//实现两个有序数组合并为一个有序数组
func mergeArray(a, b []int) []int {
lenC := len(a) + len(b)
arrC := make([]int, lenC)
indexA := 0
indexB := 0
indexC := 0
for indexA < len(a) && indexB < len(b) {
if a[indexA] < b[indexB] {
arrC[indexC] = a[indexA]
indexA++
indexC++
} else {
arrC[indexC] = b[indexB]
indexB++
indexC++
}
}
for indexA < len(a) {
arrC[indexC] = a[indexA]
indexA++
indexC++
}
for indexB < len(b) {
arrC[indexC] = b[indexB]
indexB++
indexC++
}
return arrC
}
//实现两个有序数组合并为一个有序数组
func mergeArrayV2(a, b []int) []int {
lenC := len(a) + len(b)
arrC := make([]int, lenC)
indexA := 0
indexB := 0
for i := 0; i < lenC; i++ {
if indexA < len(a) && indexB < len(b) && a[indexA] < b[indexB] {
arrC[i] = a[indexA]
indexA++
} else if indexA < len(a) && indexB < len(b) && a[indexA] >= b[indexB] {
arrC[i] = b[indexB]
indexB++
} else if indexA < len(a) {
arrC[i] = a[indexA]
indexA++
} else {
arrC[i] = b[indexB]
indexB++
}
}
return arrC
}
func main() {
arrA := []int{1, 3, 5, 7, 9}
arrB := []int{2, 4, 6, 8, 10}
mergeArr := mergeArrayV2(arrA, arrB)
fmt.Printf("after merge arr is: %v\n", mergeArr)
}
2. 实现一个支持动态扩容的数组
参考链接：https://segmentfault.com/a/1190000015680429?utm_source=tag-newest
3. 链表代码实现如下：
package main
import "fmt"
type Node struct {
data int
next *Node
}
type HeadNode struct {
num int
first *Node
}
//打印
func printNode(head *HeadNode) {
if head.first == nil {
fmt.Printf("node is null\n")
} else {
curNode := head.first
for curNode != nil {
fmt.Printf("data is: %v\n", curNode)
curNode = curNode.next
}
}
}
//插入
func insertNode(head *HeadNode, node *Node){
if head.first ==nil {
head.num = 1
head.first = node
} else {
curNode := head.first
for curNode.next != nil {
curNode = curNode.next
}
curNode.next = node
head.num++
}
}
// 1.单链表反转
func invertList(head *HeadNode) {
if head.first == nil {
return
}
if head.first.next == nil {
return
}
preNode := head.first
curNode := head.first.next
preNode.next = nil
for curNode.next != nil {
nextNode := curNode.next
curNode.next = preNode
preNode = curNode
curNode = nextNode
}
curNode.next = preNode
head.first = curNode
}
// 2.链表中有环检测
func checkListCycle(head *HeadNode) bool {
if head.first == nil {
return false
}
slowNode := head.first
fastNode := head.first
for fastNode.next.next != nil{
slowNode = slowNode.next
fastNode = fastNode.next.next
if slowNode == fastNode{
return true
}
}
return false
}
// 3.两个有序链表的合并
func meregeList(headFirst, headSecond *HeadNode) *HeadNode{
newHead := &HeadNode{0, nil}
firstListNode := headFirst.first
secondListNode := headSecond.first
for firstListNode != nil && secondListNode != nil{
if firstListNode.data < secondListNode.data {
tmpNode := &Node{firstListNode.data, nil}
insertNode(newHead, tmpNode)
firstListNode = firstListNode.next
} else {
tmpNode := &Node{secondListNode.data, nil}
insertNode(newHead, tmpNode)
secondListNode = secondListNode.next
}
}
for firstListNode != nil{
tmpNode := &Node{firstListNode.data, nil}
insertNode(newHead, tmpNode)
firstListNode = firstListNode.next
}
for secondListNode != nil{
tmpNode := &Node{secondListNode.data, nil}
insertNode(newHead, tmpNode)
secondListNode = secondListNode.next
}
return newHead
}
// 4.删除链表倒数第n个结点
func deleteNodeByNum(head *HeadNode, num int){
firstNode := head.first
secondNode := head.first
//两个node之前差值为num
for i:=1; i<=num+1; i++{
firstNode = firstNode.next
}
for firstNode != nil {
firstNode = firstNode.next
secondNode = secondNode.next
}
secondNode.next = secondNode.next.next
}
// 5.求链表的中间结点
func selectMiddleNode(head *HeadNode) *Node{
if head.first == nil {
return nil
}
slowNode := head.first
fastNode := head.first
for fastNode != nil && fastNode.next != nil {
slowNode = slowNode.next
fastNode = fastNode.next.next
}
return slowNode
}
func main(){
head := &HeadNode{0, nil}
insertNode(head, &Node{1, nil})
insertNode(head, &Node{3, nil})
insertNode(head, &Node{5, nil})
insertNode(head, &Node{7, nil})
printNode(head)
fmt.Printf("all node num is: %v\n", head.num)
//1.反转链表
//invertList(head)
//printNode(head)
//head.first.next.next.next = head.first.next
//2.检测是否存在环
flag := checkListCycle(head)
fmt.Printf("list is have cycle flag is: %v\n\n", flag)
head2 := &HeadNode{0, nil}
insertNode(head2, &Node{2, nil})
insertNode(head2, &Node{4, nil})
insertNode(head2, &Node{6, nil})
insertNode(head2, &Node{8, nil})
printNode(head2)
fmt.Printf("after merege is\n\n")
//3.合并两个有序链表
newHead := meregeList(head, head2)
printNode(newHead)
fmt.Printf("after delete node by num desc is\n\n")
// 4.删除链表倒数第n个结点
deleteNodeByNum(newHead, 3)
printNode(newHead)
// 5.求链表的中间结点
midNode := selectMiddleNode(newHead)
fmt.Printf("mid node is: %v\n", midNode)
}
优质博文参考链接：https://www.cnblogs.com/huangliang-hb/p/10855558.html
有疑问加站长微信联系（非本文作者）
