go实现反转链表
反转链表首先讨论特殊节点
如果节点在首位，则反转之后，首位节点的next值为nil。
func reverse(head *ListNode) *ListNode {
bnode := head//设置默认遍历的前节点，为head
temp := head.Next//从head.next节点开始遍历链表
flage := 0//设置一个标记，用于判断是否为第一个节点
var lnext *ListNode//用于临时保存下一个节点
for temp != nil {//遍历当
lnext = temp.Next//先将遍历节点的下一个节点进行保存
temp.Next = bnode//节点反转，将此节点的next值进行更改，更改为上一个节点
if flage == 0 {//如果是第一个节点，则flage为0
bnode.Next = nil//第一个节点翻转后的next值为nil
flage = 1//将flage值进行更改，避免之后的节点的next值被更改为nil
}
bnode = temp//将节点进行更新，前节点更改为遍历节点
temp = lnext//节点进行更新，由于之前temp.next值已经被更改，但是temp.next值被保存在变量中所以temp = lnext
}
return bnode//返回bnode节点，不能返回temp节点，temp为空，因为temp为空是跳出for循环的标志
}
补充：golang 链表逆序反转输出
链表逆序输出案例代码
//如何实现链表的逆序
package main
import "fmt"
type studentNode struct {
no int
name string
age int
next *studentNode
pre *studentNode
}
func reversePrint(head *studentNode) {
//1.创建一个辅助结点
temp := head
//2.判断这是不是一个空链表
if temp.next == nil { //说明是一个空链表
return
}
//3.让temp指向这个双向链表的最后结点
for {
if temp.next == nil {
break
}
temp = temp.next
} //循环结束则已经指向双向链表的最后结点
//4.遍历这个链表
for{
fmt.Printf("%d,%s,%d==>",temp.no,temp.name,temp.age)
temp=temp.pre//依次向前
if temp.pre==nil{//判断是不是到了链表头
break
}
}
}
func insertStudentNode(head *studentNode, newStudentNode *studentNode) {
//思路：
//1.先找到该链表的最后这个结点
//2.创建一个辅助结点
temp := head
for {
if temp.next == nil { //表示找到最后
break
}
temp = temp.next //让temp不断的指向下一个结点
}
//3.将newStudentNode加入到链表的最后
temp.next = newStudentNode
newStudentNode.pre=temp
}
//正序打印这个双向链表
func originalList(head *studentNode) {
//1.创建一个辅助结点
temp:=head
//2.先判断这个链表是否是空链表
if temp.next==nil{
fmt.Println("这是一个空链表")
return
}
//3.遍历这个链表
for{
fmt.Printf("%d,%s,%d==>",temp.next.no,temp.next.name,temp.next.age)
temp=temp.next
if temp.next == nil{
break
}
}
}
//创建一个双向链表
func createlink()*studentNode {
//1.先创建一个头结点
head := &studentNode{}
//2.创建一个新的studentNode
stuLisa := &studentNode{
no: 1,
name: "Lisa",
age: 24,
}
stuBob := &studentNode{
no: 2,
name: "Bob",
age: 25,
}
stuNick := &studentNode{
no: 3,
name: "Nick",
age: 27,
}
stuMark := &studentNode{
no: 4,
name: "Mark",
age: 29,
}
//3.加入结点
insertStudentNode(head, stuLisa)
insertStudentNode(head, stuBob)
insertStudentNode(head, stuNick)
insertStudentNode(head, stuMark)
return head
}
//逆序打印这个双向链表
func main() {
head :=createlink()
fmt.Println("正序打印")
originalList(head)
fmt.Println()
fmt.Println("逆序打印")
reversePrint(head)
}
结果
以上为个人经验，希望能给大家一个参考，也希望大家多多支持我们。如有错误或未考虑完全的地方，望不吝赐教。
相关推荐
-
Go实现双向链表的示例代码
本文介绍什么是链表,常见的链表有哪些,然后介绍链表这种数据结构会在哪些地方可以用到,以及 Redis 队列是底层的实现,通过一个小实例来演示 Redis 队列有哪些功能,最后通过 Go 实现一个双向链表. 目录 1.链表 1.1 说明 1.2 单向链表 1.3 循环链表 1.4 双向链表 2.redis队列 2.1 说明 2.2 应用场景 2.3 演示 3.Go双向链表 3.1 说明 3.2 实现 4.总结 5.参考文献 1.链表 1.1 说明 链表(Linked list)是一种常见的基础数据
-
详解go语言单链表及其常用方法的实现
目的 在刷算法题中经常遇到关于链表的操作,在使用go语言去操作链表时不熟悉其实现原理,目的是为了重温链表这一基础且关键的数据结构. 1.链表的特点和初始化 1.1.链表的特点 用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的) 1.2.结点 结点(node) 数据域 => 存储元素信息 指针域 => 存储结点的直接后继,也称作指针或链 首元结点 是指链表中存储的第一个数据元素的结点 头结点 是在首元结点之前附设的一个结点,其指针域指向首元结点(非必须) 头指
-
python/golang 删除链表中的元素
先用使用常规方法,两个指针: golang实现: type Node struct { value int next *Node } type Link struct { head *Node tail *Node lenth int } // 向链表中添加元素 func (link *Link) add(v int) { if link.lenth == 0 { // 当前链表是空链表 link.head = &Node{v, nil} link.tail = link.head link.l
-
python/golang实现循环链表的示例代码
循环链表就是将单链表的末尾指向其头部,形成一个环.循环链表的增删操作和单链表的增删操作 区别不大.只是增加时,需要考虑空链表增加第一个节点的特殊情况:删除时需考虑删除节点是头/尾节点,和链表中只有一个节点的特殊情况. golang实现: type Node struct { value int next *Node } type Circle struct { tail *Node lenth int } // 增加节点: func (c *Circle) add(value int) { ne
-
Go语言单链表实现方法
本文实例讲述了Go语言单链表实现方法.分享给大家供大家参考.具体如下: 1. singlechain.go代码如下: 复制代码 代码如下: ////////// //单链表 -- 线性表 package singlechain //定义节点 type Node struct { Data int Next *Node } /* * 返回第一个节点 * h 头结点 */ func GetFirst(h *Node) *Node { if h.Next == nil {
-
golang双链表的实现代码示例
双链表的实现 基本概念 每一个节点都存储上一个和下一个节点的指针 实现思路 创建一个节点结构体 每个节点都有上节点指针与下节点指针 每个节点都有一个key => value 创建一个链表结构体 链表容量大小属性 链表大小属性 链表锁, 实现并发安全 链表头节点 链表尾节点 实现链表操作方法 添加头部节点操作AppendHead 添加尾部节点操作AppendTail 追加尾部节点操作Append 插入任意节点操作Insert 删除任意节点操作Remove 删除头部节点操作RemoveHead 删除
-
Java语言实现反转链表代码示例
问题描述 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的链表的头结点.链表结点如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } 思路1: 要想反转链表,对于结点i,我们要把它的next指向它的前趋,因此我们需要保存前趋结点,同时,如果我们已经把i的next重新赋值,会无法找到i的后继,因此,在重新赋值之前,我们要保存i的后继. 代码:
-
C++数据结构与算法之反转链表的方法详解
本文实例讲述了C++数据结构与算法之反转链表的方法.分享给大家供大家参考,具体如下: 算法概述:要求实现将一条单向链表反转并考虑时间复杂度. 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销. 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表. 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表. 算法实现: 构建链表结构 /
-
基于Python实现2种反转链表方法代码实例
题目: 反转一个单链表. 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表.你能否用两种方法解决这道题? 思路: 主要需要注意反转过程中不要丢了节点.可以使用两个指针,也可以使用三个指针. Python解法一: class Solution: def reverseList(self, head): cur, prev = head, None while
-
Java 利用栈来反转链表和排序的操作
栈是一个特殊的数据结构,特点是先进后出(First In Last Out 简称FILO),这种特殊的数据结构,可以用在对链表做反转中,或者字符串逆序,因为要把头变成尾,尾变成头,栈这种结构最合适不过了,下面来看看如何用栈来做链表的反转. package com.xxx.algorithm.sort; import java.util.Stack; public class LinkedListReverse { public static Node reverseLinkedList(Node
-
go实现反转链表
反转链表首先讨论特殊节点 如果节点在首位,则反转之后,首位节点的next值为nil. func reverse(head *ListNode) *ListNode { bnode := head//设置默认遍历的前节点,为head temp := head.Next//从head.next节点开始遍历链表 flage := 0//设置一个标记,用于判断是否为第一个节点 var lnext *ListNode//用于临时保存下一个节点 for temp != nil {//遍历当 lnext =
-
C++相交链表和反转链表详解
目录 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点.如果两个链表没有交点,返回 null . 思路 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表. 双指针思路 递归 总结 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点.如果两个链表没有交点,返回 null . 思路 简单来说,就是求两个链表交点节点的 指针. 这里同学们要注意,交点不是数值相等,而是指针相等. 为了方便举例,假设节点
-
单链表反转python实现代码示例
单链表的反转可以使用循环,也可以使用递归的方式 1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可. 代码: class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head): #循环的方法反转链表 if head is None or head.next is None: return head; pre=None; c
-
PHP实现链表的定义与反转功能示例
本文实例讲述了PHP实现链表的定义与反转功能.分享给大家供大家参考,具体如下: PHP定义链表及添加.移除.遍历等操作: <?php class Node { private $Data;//节点数据 private $Next;//下一节点 public function setData($value){ $this->Data=$value; } public function setNext($value){ $this->Next=$value; } public functio
-
python实现反转部分单向链表
题目: 给定一个单链表的头指针 head, 以及两个整数 a 和 b,在单链表中反转 linked_list[a-b] 的结点,然后返回整个链表的头指针. 例如: 单链表[1000, 5, 12, 100, 45, 'cecil', 999], a = 4, b = 6, 返回的链表是[1000, 5, 12, 100, 999, 'cecil', 45],也就是说, a 和 b分别为索引值.如果a 和 b 超过了索引范围就返回错误. 代码: 我写的不够简洁,比较繁琐,但是能跑通,繁琐的原因在于
-
Python实现链表反转的方法分析【迭代法与递归法】
本文实例讲述了Python实现链表反转的方法.分享给大家供大家参考,具体如下: Python实现链表反转 链表反转(while迭代实现): 链表的反转引入一个cur_node变量,表示当前节点:同时需要引入一个变量new_link表示反转后的新链表:while循环内还需中间变量tmp存放当前节点的后继节点,防止原链表数据丢失. 在while循环内(循环条件为 cur_node !=None,若设置为cur_node.next将导致最后一个节点无法反转到新链表): 首先需要将当前节点的后继节点传递