Python递归以及非递归实现反转链表

本文阅读 1 分钟
首页 Python笔记 正文

需要注意三个问题:输入的链表头指针为None或者整个链表只有一个结点时,反转后的链表出现断裂,返回的翻转之后的头节点不是原始链表的尾结点。因此需要引入一个翻转后的头结点,以及一个指向当前结点的指针,一个指向当前结点前一个结点的指针,一个指向当前结点后一个结点的指针,防止出现断裂。

  1. '''
  2. 反转链表
  3. 输入一个链表,反转链表后,输出链表的所有元素
  4. '''
  5. # -*- coding:utf-8 -*-
  6. class ListNode:
  7. def __init__(self, x):
  8. self.val = x
  9. self.next = None
  10. class Solution:
  11. # 返回ListNode
  12. def ReverseList(self, pHead):
  13. pReversedHead = None
  14. pNode = pHead
  15. pPrev = None
  16. while pNode != None:
  17. pNext = pNode.next
  18. if pNext == None:
  19. pReversedHead = pNode
  20. pNode.next = pPrev
  21. pPrev = pNode
  22. pNode = pNext
  23. return pReversedHead
  24. # 递归实现反转链表
  25. def ReverseListRec(self, pHead):
  26. if not pHead or not pHead.next:
  27. return pHead
  28. else:
  29. pReversedHead = self.ReverseList(pHead.next)
  30. pHead.next.next = pHead
  31. pHead.next = None
  32. return pReversedHead
  33. node1 = ListNode(10)
  34. node2 = ListNode(11)
  35. node3 = ListNode(13)
  36. node1.next = node2
  37. node2.next = node3
  38. S = Solution()
  39. p = S.ReverseList(node1)
  40. print(p.next.val)
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python链表中倒数第k个结点
« 上一篇 01-21
Python合并两个排序的链表
下一篇 » 01-21

发表评论

惪特博客
  • 文章总数:
    18501 篇
  • 评论总数:
    53360 条
  • 标签总数:
    8881 个
  • 总浏览量:
    23359725 次
  • 最后更新:
    6天前

最多点赞

随便看看

标签TAG