40.Go语言·数据结构·环形单向链表

main.go

// Go语言·数据结构
package main

import (
    "fmt"
)

var content string = `
————————————————Go语言·数据结构————————————————————
一、链表
    是有序的列表，

二、环形单向链表

`


// 定义一个节点
type Cat struct {
    id       int
    name     string
    next     *Cat   //表示指向下一个节点
}

// 加入
func Push(headNode *Cat,nextNode *Cat){
    // 判断是不是添加第一只猫
    if headNode.next == nil {
        headNode.id   = nextNode.id
        headNode.name = nextNode.name
        headNode.next = headNode
        return 
    }

    //定义一个临时变量，找到环形的最后的节点
    tmp := headNode
    for {
        if tmp.next == headNode{
            break
        }
        tmp = tmp.next
    }

    // 加入到链表中
    tmp.next = nextNode
    nextNode.next = headNode
}

// 删除
func Pop(headNode *Cat,num int) (head *Cat){
    var flag = false
    tmp := headNode
    helper := headNode
    // 没有节点
    if tmp.next == nil {
        fmt.Println("空链表~~~")
        return headNode
    }

    // 只有一个节点
    if tmp.next == headNode {
        tmp.next = nil
        return headNode
    }

    // helper指向最后一个节点
    for {
        if helper.next == headNode{
            break
        }
        helper = helper.next
    }


    // n个节点n>=2
    for {
        
        if tmp.id == num {
            if tmp == headNode {
                headNode = headNode.next
            }
            // 找到咯。我们要删除的节点
            helper.next = tmp.next
            flag = true
            break 
        }

        if flag || tmp.next == headNode {
            //最后一个节点咯。但是还没有比较
            if !flag {
                fmt.Println("没有找到你想要的~~~")
            }  
            break
        }

        // 移动比较，不参与删除
        tmp = tmp.next
        // 移动。找到节点后，参与删除 helper是tmp的上一个节点
        helper = helper.next
    }
    return  headNode
}



// 显示、打印
func ListCircleLink(headNode *Cat) {
    fmt.Println("\n环形链表的内容如下：")
    tmp := headNode
    if tmp.next == nil{
        fmt.Println("环形链表，什么也没有！")
        return 
    }

    for {
        fmt.Printf("[No.%d %v]===>",tmp.id,tmp.name)
        if tmp.next == headNode {
            fmt.Printf("[No.%d %v]",headNode.id,headNode.name)
            break
        }
        tmp = tmp.next
    }
    fmt.Println("\n***************************************")
    fmt.Println()
}


func main() {
    // 初始化一个环形链表的头结点
    headNode := &Cat{}
    cat1 := &Cat{
        id:1,
        name :"小桃",
    }
    Push(headNode, cat1)
    cat2 := &Cat{
        id:2,
        name :"小可",
    }
    Push(headNode, cat2)

    cat3 := &Cat{
        id:3,
        name :"小樱",
    }
    Push(headNode, cat3)

    ListCircleLink(headNode)

    headNode = Pop(headNode,1)

    ListCircleLink(headNode)
}