Go 反转链表、单链表的添加和显示、单链表的添加和显示控制反转

浅浅的花香味﹌ 2023-10-08 18:49 17阅读 0赞

#### 阅读目录 ####

*  链表的类型
 *   *  单链表的添加和显示
     *  单链表的添加和显示控制反转
     *  反转链表

## 链表的类型 ##

链表有很多种类型，其主要的区别是节点引用方式的区别：

*  单向
 *  双向
 *  首尾连接

### 单链表的添加和显示 ###

单链表就是单向的。

每一个节点都有一个指向下一个节点的引用，除了最后一个节点。

节点的引用部分包含下一个节点的地址。

最后一个节点的引用部分包含值 nil。

package main
    
    import "fmt"
    
    //  1、定义一个 HeroNode
    type HeroNode struct {
        
    	no       int
    	name     string
    	nickname string
    	next     *HeroNode
    }
    
    // 4、给链表出入一个节点
    // 编写第一种插入方法，在单链表的最后加入
    func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {
        
    	// 思路
    	// 4.1、先找到改链表的最后这个节点
    	// 4.2、创建一个辅助节点【跑龙套，帮忙】
    	temp := head
    	for {
        
    		// 表示找到最后
    		if temp.next == nil {
        
    			break
    		}
    		// 让temp不断的指向下一个节点
    		temp = temp.next
    	}
    	// 3、将 newHeroNode 加入到链表的最后
    	temp.next = newHeroNode
    }
    
    // 5、显示链表的所有节点信息
    func ListHeroNode(head *HeroNode) {
        
    	// 5.1、创建一个辅助节点【跑龙套，帮忙】
    	temp := head
    	// 5.2、先判断该链表是不是一个空的链表
    	if temp.next == nil {
        
    		fmt.Println("空空如也...")
    		return
    	}
    	// 5.3、遍历这个链表
    	for {
        
    		// 打印第一个值
    		fmt.Printf("[%d,%s,%s]==>",
    			temp.next.no,
    			temp.next.name,
    			temp.next.nickname)
    
    		// 判断是否链表最后一个
    		temp = temp.next
    		if temp.next == nil {
        
    			break
    		}
    	}
    }
    
    func main() {
        
    	// 2、先创建一个头节点
    	head := &HeroNode{
        }
    	// 3、创建一个新的 HeroNode
    	hero1 := &HeroNode{
        
    		no:       1,
    		name:     "宋江",
    		nickname: "及时雨",
    	}
    	// 8、创建一个新的 HeroNode
    	hero2 := &HeroNode{
        
    		no:       2,
    		name:     "卢俊义",
    		nickname: "玉麒麟",
    	}
    
    	// 6、加入
    	InsertHeroNode(head, hero1)
    	InsertHeroNode(head, hero2)
    	// 7、显示
    	ListHeroNode(head)
    }

PS E:\TEXT\test_go\one> go run .\main.go
    [1,宋江,及时雨]==>[2,卢俊义,玉麒麟]==>
    PS E:\TEXT\test_go\one>

### 单链表的添加和显示控制反转 ###

![在这里插入图片描述][efd8f71ba9ce4b6ea8c147d2f5ba1485.png]  
输入：head = \[1,2,3,4,5\]  
输出：\[5,4,3,2,1\]

### 反转链表 ###

package main
    
    import "fmt"
    
    // ListNode 链表节点
    type ListNode struct {
        
    	Val  int
    	Next *ListNode
    }
    
    // 方法一：头插法
    func reverseList(head *ListNode) *ListNode {
        
    	var ans *ListNode
    	for head != nil {
        
    		next := head.Next
    		head.Next = ans
    		ans = head
    		head = next
    	}
    	return ans
    }
    
    // 方法二：头插法
    // func reverseList(head *ListNode) *ListNode {
        
    // 	pre := new(ListNode)
    // 	pre = nil
    // 	for head != nil {
        
    // 		temp := head.Next
    // 		head.Next = pre
    // 		pre = head
    // 		head = temp
    // 	}
    // 	return pre
    // }
    
    // 方法三：递归
    // func reverseList(head *ListNode) *ListNode {
        
    // 	if head == nil {
        
    // 		return nil
    // 	}
    // 	if head.Next == nil {
        
    // 		return head
    // 	}
    // 	newHead := reverseList(head.Next)
    // 	head.Next.Next = head
    // 	head.Next = nil
    // 	return newHead
    // }
    
    func main() {
        
    	head := new(ListNode)
    	head.Val = 1
    
    	node1 := new(ListNode)
    	head.Next = node1
    	node1.Val = 2
    
    	for list := reverseList(head); list != nil; list = list.Next {
        
    		fmt.Printf("值%d", list.Val)
    	}
    }

[efd8f71ba9ce4b6ea8c147d2f5ba1485.png]: https://img-blog.csdnimg.cn/efd8f71ba9ce4b6ea8c147d2f5ba1485.png