1.1.1. 一、单向环形链表的说明:
- 单向环形链表类似于几个人手拉手组成一圈。
- 单向环形链表的节点,指向下一个节点。并且next不能为空(nil)。如果是第一个节点,它的next等于它自己。
- 元素结构如下:
type Persion struct {
Num int
Name string
next *Persion // 下一个节点
}
1.1.2. 二、单向环形列表的实现:
1、添加节点:
//增加一个节点
func InsertNode(head *Persion, newNode *Persion) {
if head.next == nil { //判断是不是第一个元素
head.Num = newNode.Num
head.Name = newNode.Name
head.next = head //构成一个环形
fmt.Println(newNode, "加入到环形的链表")
return
}
// 最终找到的temp,是head之前的一个节点
temp := head
for {
if temp.next == head {
break
}
temp = temp.next //下一个结点
}
//把newNode 插入 temp 和 head之间
temp.next = newNode
newNode.next = head
}
2、显示节点信息:
//显示所有结点信息
func ListNode(head *Persion) {
temp := head
if temp.next == nil {
fmt.Println("空空如也的环形链表...")
return
}
for {
fmt.Printf("[num=%d name=%s] ->", temp.Num, temp.Name)
if temp.next == head { // 从head 开始遍历,到head为止。
break
}
temp = temp.next
}
}
3、删除节点:
//删除节点
func DelNode(head *Persion, id int) *Persion {
//空链表
if head.next == nil {
fmt.Println("这是一个空的环形链表,不能删除")
return head
}
if head.next == head { //链表只有一个结点
if head.Num == id {
head.next = nil //删除
}
return head
}
//helper 设置为最后一个节点。 head 是最前一个。helper 在 head之前
helper := head
for {
if helper.next == head {
break
}
helper = helper.next
}
// temp 表示查找到的num == id的节点
temp := head
flag := true //是否已经删除
for {
if temp.next == head { //比较到head之前的一个节点,也就是比较到最后了。
break
}
if temp.Num ==id {
if temp == head { //说明删除的是头结点
head = head.next //把头节点往下移动
}
//找到,删除temp节点
helper.next = temp.next
fmt.Printf("节点=%d\n", id)
flag = false
break
}
// temp 、helper 一起移动。保持一个关系helper永远是temp的上一个节点。
temp = temp.next
helper = helper.next
}
//这里还有比较一次
if flag { //如果 flag 为真,则我们上面没有删除
if temp.Num == id {
helper.next = temp.next // 删除temp节点
fmt.Printf("节点=%d\n", id)
}else {
fmt.Printf("对不起,没有 num=%d\n", id)
}
}
return head
}
说明:
1、删除一个单向环形链表的节点,需要3个变量。要删除的节点 deletedNode、要删除节点的上一个节点 preNode、要删除节点的下一个节点 nextNode。(这是因为单向链表只能往一个方向遍历。所以需要保存遍历过的值preNode,以便后面使用。)
2、删除的动作就是把 preNode 的next 设置为nextNode。要注意几个情况。
- 链表为空。
- 链表只有1个节点。
- 链表只有2个节点。
4、测试。
func main() {
//1. 先创建一个头结点
head := &Persion{}
p1 := &Persion{Num:100,Name:"张三",}
p2 := &Persion{Num:101,Name:"李四",}
p3 := &Persion{Num:99,Name:"王五",}
// 插入链表
InsertNode(head,p1)
InsertNode(head,p2)
InsertNode(head,p3)
// 显示链表
ListNode(head)
// 把头结点,更改为
head = DelNode(head,100)
head = DelNode(head,99)
head = DelNode(head,101)
ListNode(head)
}