Go 单向环形链表

单向环形链表

单向环形链表是一种特殊的单向链表。

单向链表最后一个节点的 Next 指针指向空。

而单向环形链表最后一个节点的 Next 指针指向头节点。

如图所示：

package main

import "fmt"

type CatNode struct {
    No   int
    Name string
    Next *CatNode
}

func AddCartNode(head *CatNode, newCatNode *CatNode) {
    // 判断是不是添加第一只猫
    if head.Next == nil {
        head.No = newCatNode.No
        head.Name = newCatNode.Name
        head.Next = head
    } else {
        // 定义一个临时变量，帮忙,找到环形的最后结点
        temp := head
        for {
            if temp.Next == head {
                break
            }
            temp = temp.Next
        }
        // 加入到链表中
        newCatNode.Next = head
        temp.Next = newCatNode
    }
    fmt.Println("添加成功")
}

//输出这个环形的链表
func ListCircleLink(head *CatNode) {
    temp := head
    if temp.Next == nil {
        fmt.Println("环形单链表空空如也...")
        return
    }
    fmt.Println("环形单链表打印:")
    fmt.Printf("\t")
    for {
        fmt.Printf("[No: %d Name: %s]->", temp.No, temp.Name)
        if temp.Next == head {
            break
        }
        temp = temp.Next
    }
    fmt.Println()
}

// 删除一只猫
func DelCatNode(head *CatNode, no int) *CatNode {
    temp := head
    // 定义环形链表尾部
    rear := head
    // 空链表
    if head.Next == nil {
        fmt.Println("环形单链表, 不能删除...")
        return head
    }
    // 如果只有一个结点
    if temp.Next == head && temp.No == no {
        temp.Next = nil
        return head
    }
    // 将rear定位到链表最后
    for {
        if rear.Next == head {
            break
        }
        rear = rear.Next
    }

    // 如果有两个包含两个以上结点
    flag := true
    for {
        // 如果到这来，说明我比较到最后一个【最后一个还没比较】
        if temp.Next == head {
            break
        }
        if temp.No == no {
            //说明删除的是头结点
            if temp == head {
                head = head.Next
            }
            //恭喜找到., 我们也可以在直接删除
            rear.Next = temp.Next
            fmt.Println("删除结点:")
            fmt.Printf("\t[No: %d Name: %s]\n", temp.No, temp.Name)
            flag = false
            break
        }
        // 位移, 比较<temp.No == no>
        temp = temp.Next
        // 移动 <一旦找到要删除的结点 rear>
        rear = rear.Next
    }

    // 这里还有比较一次
    if flag {
        //如果flag 为真, 则我们上面没有删除, 判断是不是删除头结点
        if temp.No == no {
            rear.Next = temp.Next
        } else {
            fmt.Printf("没有此结点[No=%d]...\n", no)
        }
    }
    return head
}

func main() {
    head := &CatNode{}
    cat1 := &CatNode{No: 1, Name: "tom1"}
    cat2 := &CatNode{No: 2, Name: "tom2"}
    cat3 := &CatNode{No: 3, Name: "tom3"}
    AddCartNode(head, cat1)
    ListCircleLink(head)
    AddCartNode(head, cat3)
    ListCircleLink(head)
    AddCartNode(head, cat2)
    ListCircleLink(head)

    head = DelCatNode(head, 3)
    ListCircleLink(head)

    head = DelCatNode(head, 4)
    ListCircleLink(head)
}