python如何实现单链表的反转

这篇文章主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

代码如下

# coding=utf-8
class Node:
  def __init__(self, data=None, next=None):
    self.data = data
    self.next = next

def Reserver(link):
  pre = link
  cur = link.next
  pre.next = None
  while cur:
    tmp = cur.next
    cur.next = pre
    pre = cur
    cur = tmp
  return pre

if __name__ == "__main__":
  node = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
  root = Reserver(node)

  while root:
    print root.data,
    root = root.next

解释一下rev函数的实现过程：

line 9-11是将原链表的第一个节点变成了新链表的最后一个节点，同时将原链表的第二个节点保存在cur中

line13-16就是从原链表的第二个节点开始遍历到最后一个节点，将所有节点翻转一遍

以翻转第二个节点为例

temp = cur.next是将cur的下一个节点保存在temp中，也就是第节点3，因为翻转后，节点2的下一个节点变成了节点1，原先节点2和节点3之间的连接断开，通过节点2就找不到节点3了，因此需要保存

cur.next = pre就是将节点2的下一个节点指向了节点1

然后pre向后移动到原先cur的位置，cur也向后移动一个节点，也就是pre = cur ,cur =temp

这就为翻转节点3做好了准备

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • Python实现针对给定单链表删除指定节点的方法

    Python实现针对给定单链表删除指定节点的方法

    本文实例讲述了Python实现针对给定单链表删除指定节点的方法.分享给大家供大家参考,具体如下: 题目: 初始化定义一个单链表,删除指定节点,输出链表 下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:给定一个单链表删除指定节点 ''' class Node(object): ''''' 节点类 ''' def __init__(self,data): self.num=data self.next=N

  • Python单链表的简单实现方法

    本文实例讲述了Python单链表的简单实现方法,分享给大家供大家参考.具体方法如下: 通常来说,要定义一个单链表,首先定义链表元素:Element.它包含3个字段: list:标识自己属于哪一个list datum:改元素的value next:下一个节点的位置 具体实现代码如下: class LinkedList(object): class Element(object): def __init__(self,list,datum,next): self._list = list self.

  • Python3实现的反转单链表算法示例

    本文实例讲述了Python3实现的反转单链表算法.分享给大家供大家参考,具体如下: 反转一个单链表. 方案一:迭代 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head): """ :type head: ListNod

  • python版本单链表实现代码

    今天看了一下数据结构的书,发现其实数据结构没有几种,线性表,数组,字符串,队列和栈,等等,其实是一回事,然后就是树结构,图结构.数据结构的理论并不难,主要是要自己写一下这些数据结构以及对应的基本的操作方法,这样就能够更快的提高. 这一篇blog写一下线性表. 线性表:分为顺序表和链表 一.顺序表 顺序表就是相对于表中的数据,地址也是顺序的,所以可以随机存取.但是在操作插入和删除元素的时候,由于要满足地址的连续性,所以要移动很多的元素位置,因此,插入或者删除一个顺序表的元素的时间复杂度是o(n).

  • python环形单链表的约瑟夫问题详解

    题目: 一个环形单链表,从头结点开始向后,指针每移动一个结点,就计数加1,当数到第m个节点时,就把该结点删除,然后继续从下一个节点开始从1计数,循环往复,直到环形单链表中只剩下了一个结点,返回该结点. 这个问题就是著名的约瑟夫问题. 代码: 首先给出环形单链表的数据结构: class Node(object): def __init__(self, value, next=0): self.value = value self.next = next # 指针 class RingLinkedL

  • 单链表反转python实现代码示例

    单链表反转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

  • python如何实现单链表的反转

    这篇文章主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码如下 # coding=utf-8 class Node: def __init__(self, data=None, next=None): self.data = data self.next = next def Reserver(link): pre = link cur = link.next pre.next = None whil

  • Python数据结构之单链表详解

    本文实例为大家分享了Python数据结构之单链表的具体代码,供大家参考,具体内容如下 # 节点类 class Node(): __slots__=['_item','_next'] # 限定Node实例的属性 def __init__(self,item): self._item = item self._next = None # Node的指针部分默认指向None def getItem(self): return self._item def getNext(self): return s

  • 看图深入理解单链表的反转

    看图深入理解单链表的反转

    如何把一个单链表进行反转? 方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转. 方法2:使用3个指针遍历单链表,逐个链接点进行反转. 方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第一个节点挪到新表的表尾. 方法4:   递归(相信我们都熟悉的一点是,对于树的大部分问题,基本可以考虑用递归来解决.但是我们不太熟悉的一点是,对于单链表的一些问题,也可以使用递归.可以认为单链表是一颗永远只有左(右)子树的树,因此可以考虑用递归来解决.或者说,因为单

  • 单链表实现反转的3种方法示例代码

    前言 单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案: 1 ,两两对换 2, 放入数组,倒置数组 3, 递归实现 代码如下: #include<stdio.h> #include<malloc.h> typedef struct Node { int data; struct Node *pnext; } Node,*pnode; pnode CreateNode() { pnode phead=(pnode)malloc(sizeof(Node)); if(ph

  • python版单链表反转

    python版单链表反转

    本文实例为大家分享了vue + element ui实现锚点定位的具体代码,供大家参考,具体内容如下 代码如下: class Node(object):     def __init__(self, elem, next_=None):         self.elem = elem         self.next = next_   def reverseList(head):     if head == None or head.next==None:  # 若链表为空或者仅一个数就

  • python反转单链表算法题

    python反转单链表算法题

    现在算法是大厂面试的必考题,而且越来越难,已经不是简单的列表,字符串操作了,会涉及到各种数据结结构.单链表的反转也是经常考的一道题,里面故在此记录一下. 1.链表的特点: 顺序存储元素,但是元素在空间上是不连续的,所以在链表每个元素中除了存储元素的值,还会存储下一个元素的地址,单链表的话就只有指向下一个元素的指针,双向链表的话还会有指向前一个元素的指针.正是由于链表以上的存储特点,在做插入和删除操作时只需要断开指针的连接,不需要移动后面的数据,所以对链表修改的效率会很高,但是查找的效率会很低,这

  • 用python介绍4种常用的单链表翻转的方法小结

    如何把一个单链表进行反转? 方法1:将单链表储存为数组,然后按照数组的索引逆序进行反转. 方法2:使用3个指针遍历单链表,逐个链接点进行反转. 方法3:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第一个节点挪到新表的表尾. 方法4: 递归(相信我们都熟悉的一点是,对于树的大部分问题,基本可以考虑用递归来解决.但是我们不太熟悉的一点是,对于单链表的一些问题,也可以使用递归.可以认为单链表是一颗永远只有左(右)子树的树,因此可以考虑用递归来解决.或者说,因为单链表

  • Java数据结构与算法之单链表深入理解

    Java数据结构与算法之单链表深入理解

    目录 一.单链表(Linked List)简介 二.单链表的各种操作 1.单链表的创建和遍历 2.单链表的按顺序插入节点 以及节点的修改 3.单链表节点的删除 4.以上单链表操作的代码实现 (通过一个实例应用) 三.单链表常见面试题 1.求单链表中节点的个数 2.查找单链表中的倒数第K个节点[新浪面试题] 3.单链表的反转[腾讯面试题,有点难度] 4.从尾到头打印单链表 一.单链表(Linked List)简介 二.单链表的各种操作 1.单链表的创建和遍历 2.单链表的按顺序插入节点 以及节点的

  • Java单链表的增删改查与面试题详解

    Java单链表的增删改查与面试题详解

    目录 一.单链表的增删改查 1.创建结点 2.单链表的添加操作 3.单链表的删除操作 4.单链表的有效结点的个数 二.大厂面试题 一.单链表的增删改查 1.创建结点 单链表是由结点连接而成,所以我们首先要创建结点类,用于对结点进行操作.定义data属性 表示序号,定义name属性表示结点存放的数据信息,定义next属性表示指向下一个结点.构造器只需要放入data属性和name属性,重写toString方法方便打印结点信息. public class Node { public int data;

随机推荐