温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Python如何实现链表反转

发布时间:2021-03-23 13:45:23 来源:亿速云 阅读:235 作者:小新 栏目:开发技术

小编给大家分享一下Python如何实现链表反转,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!

Python实现链表反转

链表反转(while迭代实现):

  • 链表的反转引入一个cur_node变量,表示当前节点;同时需要引入一个变量new_link表示反转后的新链表;while循环内还需中间变量tmp存放当前节点的后继节点,防止原链表数据丢失。

  • 在while循环内(循环条件为 cur_node !=None,若设置为cur_node.next将导致最后一个节点无法反转到新链表):

    • 首先需要将当前节点的后继节点传递给中间变量tmp

    • 当前节点指向新链表new_link

    • 当前节点指向新链表new_link后,新链表头结点更新为当前节点cur_node

    • 将中间变量tmp传递给cur_node,开始新一轮循环

    • 循环结束后返回 new_link

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

  @staticmethod
  def reverse(head):
    cur_node = head # 当前节点
    new_link = None # 表示反转后的链表
    while cur_node != None:
      tmp = cur_node.next # cur_node后续节点传递给中间变量
      cur_node.next = new_link  # cur_node指向new_link
      new_link = cur_node  # 反转链表更新,cur_node为新的头结点
      cur_node = tmp  # 原链表节点后移一位
    return new_link

link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))
root = Node.reverse(link)
while root:
    print(root.value)
    root =root.next

运行结果:

9
8
7
6
5
4
3
2
1

递归实现:

  • 递归实现与while实现不同在于递归首先找到新链表的头部节点,然后递归栈返回,层层反转

  • 首先找到新链表的头结点(即遍历到原链表的最后一个节点返回最后节点)

  • 执行函数体后续代码,将原链表中的尾节点指向原尾节点的前置节点

  • 前置节点的指针指向None(防止出现死循环)

  • 返回新链表的头部节点至上一层函数,重复以上操作

  def reverse2(head):
    if head.next == None: # 递归停止的基线条件
      return head
    new_head = reverse2(head.next)
    head.next.next = head # 当前层函数的head节点的后续节点指向当前head节点
    head.next = None # 当前head节点指向None
    return new_head

以上是“Python如何实现链表反转”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI