python算法题 链表反转

链表的反转是一个很常见、很基础的数据结构题，输入一个单向链表，输出逆序反转后的链表，如图：上面的链表转换成下面的链表。实现链表反转有两种方式，一种是循环迭代，另外一种方式是递归。

第一种方式：循坏迭代

循坏迭代算法需要三个临时变量：pre、head、next，临界条件是链表为None或者链表就只有一个节点。

# encoding: utf-8
class Node(object):
def __init__(self):
self.value = None
self.next = None
def __str__(self):
return str(self.value)
def reverse_loop(head):
if not head or not head.next:
return head
pre = None
while head:
next = head.next # 缓存当前节点的向后指针，待下次迭代用
head.next = pre # 这一步是反转的关键，相当于把当前的向前指针作为当前节点的向后指针
pre = head # 作为下次迭代时的（当前节点的）向前指针
head = next # 作为下次迭代时的（当前）节点
return pre # 返回头指针，头指针就是迭代到最后一次时的head变量（赋值给了pre）

测试一下：

if __name__ == '__main__':
three = Node()
three.value = 3
two = Node()
two.value = 2
two.next = three
one = Node()
one.value = 1
one.next = two
head = Node()
head.value = 0
head.next = one
newhead = reverse_loop(head)
while newhead:
print(newhead.value, )
newhead = newhead.next

输出：

3
2
1
0
2

第二种方式：递归

递归的思想就是：

head.next = None
head.next.next = head.next
head.next.next.next = head.next.next
...
...

head的向后指针的向后指针转换成head的向后指针，依此类推。

实现的关键步骤就是找到临界点，何时退出递归。当head.next为None时，说明已经是最后一个节点了，此时不再递归调用。

def reverse_recursion(head):
if not head or not head.next:
return head
new_head = reverse_recursion(head.next)
head.next.next = head
head.next = None
return new_head

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

赞 (0)

相关推荐

  • 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实现代码示例

    单链表的反转可以使用循环,也可以使用递归的方式 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实现单向链表详解

    本文研究的主要是Python中实现单向链表的相关内容,具体如下. 什么是链表 链表顾名思义就是-链 链表是一种动态数据结构,他的特点是用一组任意的存储单元存放数据元素.链表中每一个元素成为"结点",每一个结点都是由数据域和指针域组成的.跟数组不同链表不用预先定义大小,而且硬件支持的话可以无限扩展. 链表与数组的不同点: 数组需要预先定义大小,无法适应数据动态地增减,数据小于定义的长度会浪费内存,数据超过预定义的长度无法插入.而链表是动态增删数据,可以随意增加. 数组适用于获取元素的操作

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

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

  • python算法题 链表反转详解

    python算法题 链表反转详解

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

  • python 算法题——快乐数的多种解法

    题目描述: 编写一个算法来确定一个数字是否"快乐". 快乐的数字按照如下方式确定:从一个正整数开始,用其每位数的平方之和取代该数,并重复这个过程,直到最后数字要么收敛等于1且一直等于1,要么将无休止地循环下去且最终不会收敛等于1.能够最终收敛等于1的数就是快乐的数字. 例如:19是一个快乐数字,计算过程如下: 1^2+9^2=82 8^2+2^2=68 6^2+8^2=100 1^2+0^2+0^2=1 要求:当输入快乐的数字时,输出True,否则输出False. 思路: 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:  # 若链表为空或者仅一个数就

  • Python实现链表反转的方法分析【迭代法与递归法】

    本文实例讲述了Python实现链表反转的方法.分享给大家供大家参考,具体如下: Python实现链表反转 链表反转(while迭代实现): 链表的反转引入一个cur_node变量,表示当前节点:同时需要引入一个变量new_link表示反转后的新链表:while循环内还需中间变量tmp存放当前节点的后继节点,防止原链表数据丢失. 在while循环内(循环条件为 cur_node !=None,若设置为cur_node.next将导致最后一个节点无法反转到新链表): 首先需要将当前节点的后继节点传递

  • Python实现的数据结构与算法之链表详解

    Python实现的数据结构与算法之链表详解

    本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin

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

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

  • python算法与数据结构之单链表的实现代码

    =一.链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,操作复杂.由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是

  • Python猜数字算法题详解

    今天刷的第一道算法题,先拿一道简单点的试试手,这道题目的要求是: 两个人甲乙在猜数字,甲先从1,2,3三个数字中随机抽3次,结果是guess.乙随后也随机抽三次,结果是answer.然后对比甲乙两个人的结果.示例如下: guess:[1,2,3], answer: [1, 2, 3] 那么结果就是猜对了3次 guess: [1,2,3] answer:[3,2,1] 那么结果就是猜对了1次 guess: [1,2,3], answer:[3, 3,1] 那么结果就是猜对了0次 即将guess和a

随机推荐