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:  # 若链表为空或者仅一个数就直接返回
        return head 
    pre = None
    next = None
    while(head != None): 
        next = head.next     # 1
        head.next = pre     # 2
        pre = head      # 3
        head = next      # 4
    return pre

if __name__ == '__main__':
    l1 = Node(3)    # 建立链表3->2->1->9->None
    l1.next = Node(2)
    l1.next.next = Node(1)
    l1.next.next.next = Node(9)
    l = reverseList(l1)
    print (l.elem, l.next.elem, l.next.next.elem, l.next.next.next.elem)

原始单链表：

反转后单链表：

反转过程如下：

第一步：next = head.next
将 head.next 赋值给 next 变量，即next 指向了节点2，先将节点2 保存起来。

第二步：head.next = pre （初始pre==None）
将 pre 变量赋值给 head.next，即 此时节点1 指向了 None

第三步：pre = head
将 head 赋值给了 pre，即 pre 指向节点1，将节点1 设为“上一个节点”

第四步：head = next
将 next 赋值给 head，即 head 指向了节点2，此时节点2 设为“头节点”

第一次循环完毕，进入第二次循环，如下图：

第一步：next = head.next
将 head.next 赋值给 next 变量，即 next 指向了节点3，先将节点3 保存起来。

第二步：head.next = pre （此时的pre已经不为None）
将 pre 赋值给 head.next，pre 在上一次循环的时候指向了节点1，那么这一步的意义就是节点2 指向了 节点1，完成1和2节点的反转。

第三步：pre = head
将 head 赋值给了 pre，即 pre 指向节点2，将节点2 设为“上一个节点”

第四步：head = next
将 next 赋值给 head，即 head 指向了节点3。此时节点3 设为“头节点”

第二次循环完毕，以此类推！第三次第四次第五次循环。最后反转成如下图

若干注意点：

(1)帮助记忆图：

(2)当前头节点的下一个节点一定要保存（比如：当前头节点为2，先将节点3 保存起来）

(3)实现反转的key point: head.next = pre

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

赞 (0)

相关推荐

  • 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实现单链表中元素的反转

    Python实现单链表中元素的反转

    给定一个单链表,将其反转.其实很容易想到,只需要修改每个结点的指针指向:即令后一个结点指向前一个结点,并且将表头指针指向最后一个结点即可. 这个过程可以用循环实现,也可以用递归来实现. 1.用循环来实现: class LNode:     def __init__(self, elem):         self.elem = elem         self.pnext = None   def reverse(head):     if head is None or head.pnex

  • 单链表反转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反转单链表算法题

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

  • 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:  # 若链表为空或者仅一个数就

  • C语言实现单链表反转

    一.理解指针 看懂链表的结构并不是很难,但是一旦把它和指针混在一起,就很容易让人摸不着头脑.所以,要想写对链表代码,首先就要理解好指针. 有些语言有"指针"的概念,比如 C 语言:有些语言没有指针,取而代之的是"引用",比如 Java.Python.不管是"指针"还是"引用",实际上,它们的意思都是一样的,都是存储所指对象的内存地址. 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变

  • C++和python实现单链表及其原理

    C++和python实现单链表及其原理

    目录 一.链表的基本概念 二.单链表 1.python实现 (1)节点设计 (2)链表类:Single_Linked_List (3)判断链表是否为空:is_empty()函数 (4)头插法:add()函数 (5)尾插法:append()函数 (6)在任意位置插入:insert()函数 (7)计算链表长度:get_length()函数 (8)遍历所有节点:traversal()函数 (9)搜索:search()函数 (10)删除:delete()函数 2.C++实现 (1)节点设计 (2)链表类

  • python实现单链表中删除倒数第K个节点的方法

    本文实例为大家分享了python实现单链表中删除倒数第K个节点的具体代码,供大家参考,具体内容如下 题目: 给定一个链表,删除其中倒数第k个节点. 代码: class LinkedListAlgorithms(object): def __init__(self): pass def rm_last_kth_node(self, k, linked_list): # 删除倒数第 K 个节点,针对单链表的 if linked_list.is_empty(): print 'The given li

  • Java实现单链表反转的多种方法总结

    Java实现单链表反转的多种方法总结

    对于单链表不熟悉的可以看一下基于Java实现单链表的增删改查 一.原地反转 1.新建一个哨兵节点下一结点指向头结点 2.把待反转链表的下一节点插入到哨兵节点的下一节点 反转之前的链表:1–>2–>3–>4>–>5 加入哨兵节点:dummp–>1–>2–>3–>4>–>5 原地反转: 定义:prev=dummp.next; pcur=prev.next; prev.next=pcur.next; pcur.next=dummp.next; d

  • Java单链表反转图文教程

    Java单链表反转图文教程

    前言 最近在回顾链表反转问题中,突然有一些新的发现和收获,特此整理一下,与大家分享

  • python实现单链表的方法示例

    前言 首先说下线性表,线性表是一种最基本,最简单的数据结构,通俗点讲就是一维的存储数据的结构. 线性表分为顺序表和链接表: 顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,称为线性表的顺序存储结构或顺序映像: 链式表示指的是用一组任意的存储单元存储线性表中的数据元素,称为线性表的链式存储结构.而他既可以是连续的也可以不连续,是通过一个与后继结点的连接信息构建起来的. *顺序表(这个不是本次重点,简单介绍一下) 顺序表是用一段连续的存储单元依次存储数据元素,查找元素是很方便的,但是

  • python算法题 链表反转

    python算法题 链表反转

    链表的反转是一个很常见.很基础的数据结构题,输入一个单向链表,输出逆序反转后的链表,如图:上面的链表转换成下面的链表.实现链表反转有两种方式,一种是循环迭代,另外一种方式是递归. 第一种方式:循坏迭代 循坏迭代算法需要三个临时变量:pre.head.next,临界条件是链表为None或者链表就只有一个节点. # encoding: utf-8 class Node(object): def __init__(self): self.value = None self.next = None de

随机推荐