go 实现单向环形单向链表

叁歲伎倆 2021-07-24 11:37 542阅读 0赞

# 一 需求 #

完成单向环形链表的增加、删除和遍历。

# 二 图解 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

# 三 代码 #

package main
    
    import (
    	"fmt"
    )
    
    // 猫结构体
    type CatNode struct {
    	no   int    // 猫猫的编号
    	name string // 名称
    	next *CatNode
    }
    
    // 插入
    func InsertCatNode(head *CatNode, newCatNode *CatNode) {
    	// 第一只猫加入前，head 的 next 为 nil
    	if head.next == nil {
    		head.no = newCatNode.no
    		head.name = newCatNode.name
    		head.next = head // 构成一个环形
    		fmt.Println(newCatNode, "加入到环形的链表")
    		return
    	}
    
    	// 临时变量，定位到环形的最后结点
    	temp := head
    	for {
    		if temp.next == head {
    			break
    		}
    		temp = temp.next
    	}
    	// 新猫节点加入到链表中
    	temp.next = newCatNode
    	newCatNode.next = head
    
    }
    
    // 输出这个环形的链表
    func ListCircleLink(head *CatNode) {
    	fmt.Println("环形链表的情况如下：")
    	temp := head
    	if temp.next == nil {
    		fmt.Println("空空如也的环形链表...")
    		return
    	}
    	for {
    		fmt.Printf("猫的信息为=[id=%d name=%s] ->\n", temp.no, temp.name)
    		if temp.next == head {
    			break
    		}
    		temp = temp.next
    	}
    }
    
    // 删除一只猫
    func DelCatNode(head *CatNode, id int) *CatNode {
    	temp := head
    	helper := head
    	// 空链表
    	if temp.next == nil {
    		fmt.Println("这是一个空的环形链表，不能删除")
    		return head
    	}
    
    	// 如果只有一个结点
    	if temp.next == head {
    		if temp.no == id {
    			temp.next = nil
    		}
    		return head
    	}
    
    	// 将 helper 定位到环形链表最后一个节点
    	for {
    		if helper.next == head {
    			break
    		}
    		helper = helper.next
    	}
    
    	// 如果有两个和两个以上结点
    	flag := true
    	for {
    		if temp.next == head { // temp 已经到环形链表最后一个节点，但还是没找到
    			break
    		}
    		if temp.no == id { // 找到了
    			if temp == head { // 删除的是头结点
    				head = head.next // 头指针的位置往后移动一下
    			}
    			// 找到了，删除
    			helper.next = temp.next
    			fmt.Printf("猫猫=%d\n", id)
    			flag = false
    			break
    		}
    		temp = temp.next     // 移动
    		helper = helper.next // 移动，它永远跟在 temp 后面，并且只相差一个节点
    	}
    	// 这里还要比较一次，比较环形链表的最后一个节点
    	if flag { // 如果flag 为真，则我们上面没有删除
    		if temp.no == id {
    			helper.next = temp.next
    			fmt.Printf("猫猫=%d\n", id)
    		} else {
    			fmt.Printf("对不起，没有no=%d\n", id)
    		}
    	}
    	return head
    }
    
    func main() {
    	// 初始化一个环形链表的头结点
    	head := &CatNode{}
    	// 创建一只猫
    	cat1 := &CatNode{
    		no:   1,
    		name: "tom1",
    	}
    	cat2 := &CatNode{
    		no:   2,
    		name: "tom2",
    	}
    	cat3 := &CatNode{
    		no:   3,
    		name: "tom3",
    	}
    	InsertCatNode(head, cat1)
    	InsertCatNode(head, cat2)
    	InsertCatNode(head, cat3)
    	ListCircleLink(head)
    	head = DelCatNode(head, 30)
    	fmt.Println()
    	fmt.Println()
    	fmt.Println()
    	ListCircleLink(head)
    }

# 四 测试 #

> &\{1 tom1 <nil>\} 加入到环形的链表
> 
> 环形链表的情况如下：
> 
> 猫的信息为=\[id=1 name=tom1\] ->
> 
> 猫的信息为=\[id=2 name=tom2\] ->
> 
> 猫的信息为=\[id=3 name=tom3\] ->
> 
> 对不起，没有no=30
> 
>  
> 
> 环形链表的情况如下：
> 
> 猫的信息为=\[id=1 name=tom1\] ->
> 
> 猫的信息为=\[id=2 name=tom2\] ->
> 
> 猫的信息为=\[id=3 name=tom3\] ->

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/af9eb155611c4e49a8cd72e233721cdc.png