剑指offer_面试题24 : 反转链表( python实现）_输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 python实现-程序员宅基地

技术标签：剑指offer 面试算法 python 算法面试算法面试题反转链表经典算法实现

反转链表( python实现）

一、题目描述

题目：反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

二、解题思路

暂略。（此处主要作为书中python实现补充）

三、代码实现

这里的链表是单向链表，为程序更直观的展示出来，首先我们先定义一个节点类，如下。

class LinkedListNode():
    def __init__ (self, value = None, next = None):
        self.value = value
        self.next = next

接下来，定义一个单向链表类（若是对单向链表操作较为熟悉，可暂时忽略，跳过此部分不影响后续程序理解），包括需要使用到的类函数，更多关于单向链表的操作可见：单向链表的创建及基本操作。

# 单链表类
class SingleLinkedList():
    # 初始化
    def __init__ (self):
        self.head = None
    
    # 判断链表是否为空
    def is_empty(self):
        if self.head is None:
            return True

    # 增加一个新的结点
    def append(self,new_value):
        node = LinkedListNode(new_value)
        if self.is_empty():
            self.head = node
        else:
            node.next = self.head
            self.head = node
    
    # 遍历整个链表，并将其值存在一个列表中
    def travel(self):
        cur = self.head
        ls = []
        while cur is not None:
            ls.append(cur.value)
            cur =cur.next
        return ls
    
    # 自行设置遍历头节点，遍历链表，并将其值存在一个列表中
    def travelSetHead(self,pHead):
        cur = pHead
        ls = []
        while cur is not None and cur.value is not None:
            ls.append(cur.value)
            cur =cur.next
        return ls

此篇博客的主要部分：Python实现题目所要求的程序如下。

def reverseLinkedList(pHead):
    nullP = LinkedListNode()
    if pHead is None:
        return nullP
    pNode = pHead
    pPrev = LinkedListNode()
    while pNode is not None:
        pNext = pNode.next
        if pNext is None:
            pReversedHead = pNode
        pNode.next = pPrev
        pPrev = pNode
        pNode = pNext
    return pReversedHead

实例化一个链表，并进行一系列添加链表节点的操作，如下。

>>> SLL = SingleLinkedList()
>>> for i in range(9):
    	SLL.append(i)
>>> print(SLL.travel())

Out:
[8, 7, 6, 5, 4, 3, 2, 1, 0]

对以上定义好的链表进行反转操作，如下。

>>> pReversedHead = reverseLinkedList(SLL.head)
>>> print(SLL.travelSetHead(pReversedHead))

Out:
[0, 1, 2, 3, 4, 5, 6, 7, 8]

考虑程序实现的鲁棒性问题，若是输入一个空的头节点，那么返回的也应该是一个None。

>>> SLL = SingleLinkedList()
>>> pReversedHead = reverseLinkedList(SLL.head)
>>> print(SLL.travelSetHead(pReversedHead))

Out:
[]

若是输入的链表只有一个节点，如下。

>>> SLL = SingleLinkedList()
>>> SLL.append(5)
>>> pReversedHead = reverseLinkedList(SLL.head)
>>> print(SLL.travelSetHead(pReversedHead))

Out:
[5]

本文链接：https://blog.csdn.net/Breathing_yang/article/details/94414666

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

使用libjpeg库实现jpeg图片的缩放（缩略图）_libjpeg缩略图-程序员宅基地

文章浏览阅读1w次，点赞2次，收藏12次。libjpeg库的交叉编译libjpeg库主要用于jpeg格式图片的编解码，其交叉编译过程如下1. 下载源码从官方网站http://www.ijg.org/files/ 下载libjpeg库的源码，本次编译过程使用的是 jpegsrc.v9a.tar.gz2. 解压源码2.1 切换到下载目录，执行 tar -xzvf jpegsrc.v9a.tar.g_libjpeg缩略图

Mysql 时间戳类型使用心得-程序员宅基地

文章浏览阅读209次。2019独角兽企业重金招聘Python工程师标准>>> ..._mysql 时间戳用什么类型合适

串口上升时间标准_JESD204B 串行接口时钟需要及其实现-程序员宅基地

文章浏览阅读221次。ChenAndyMNCsignalchainFAE摘要随着数模转换器的转换速率越来越高，JESD204B串行接口已经越来越多地广泛用在数模转换器上，其对器件时钟和同步时钟之间的时序关系有着严格需求。本文就重点讲解了JESD204B数模转换器的时钟规范，以及利用TI公司的芯片实现其时序要求。关键字：LMK04800，LMK04828,LMK1802,LMK01010,JESD204内容1.J..._204b接口支持哪种时钟

深度学习环境配置(pytorch)_mx330显卡能玩跑深度学习程序吗-程序员宅基地

文章浏览阅读2.3k次，点赞7次，收藏69次。显卡是一个硬件，需要有一个驱动才能够被我们计算机识别出来，在安装驱动的时候，会随着驱动安装一个叫做cuda driver的东西，cuda是可以让显卡进行并行运算的一个平台，当我们的计算机想利用显卡做一些并行运算的时候，它就可以通过cuda driver去操作显卡。那为什么需要虚拟环境呢，一个直接的原因，例如我们一个项目要用pytorch开发，而另一个要用tensorflow开发，这样，我们可以创建两个虚拟环境，在里面分别安装pytorch和tensorflow，两个虚拟环境中的包和库不会互相冲突。_mx330显卡能玩跑深度学习程序吗

计算复杂性理论初步（一）多项式时间归约_多项式归约-程序员宅基地

文章浏览阅读2.5k次，点赞2次，收藏12次。一、归约的意义求解一个算法问题的时候，我们往往可以直观地感受到有些问题是比较难的，有些问题是比较简单的，但是我们并不能因为没有设计出一个比较高效的算法，就说它是一个难问题，所以问题的难易是相对的，我们需要一个科学的手段来界定问题的难易我们可以用问题之间的归约，来界定两个问题之间相对难易程度的基本手段二、优化问题与判定问题很多经典的难问题都是优化问题，而一个优化问题往往可以..._多项式归约

Memory access ordering part 3 - memory access ordering in the ARM Architecture_accesses are inner-shareable-程序员宅基地

文章浏览阅读1.5k次。Memory access ordering part 3 - memory access ordering in the ARM ArchitecturePosted by leiflindholm in ARM Processors on Oct 19, 2011 6:36:00 PM In my previous posts, I have introduced th_accesses are inner-shareable

随便推点

问题解决之 RuntimeError: Couldn‘t load custom C++ ops. This can happen if your PyTorch XXX_runtimeerror: couldn't load custom c++ ops. this c-程序员宅基地

文章浏览阅读2.2w次，点赞11次，收藏66次。问题描述在深度学习环境 GPU 版 pytorch 下，运行代码出现报错，关键报错信息如下：RuntimeError: Couldn't load custom C++ ops. This can happen if your PyTorch and torchvision versions are incompatible, 大致的意思是说当前环境的 PyTorch 和 torchvision 版本不匹配，建议重新安装 PyTorch 和 torchvision。具体报错信息如下：Traceb_runtimeerror: couldn't load custom c++ ops. this can happen if your pytorch