Python递归以及非递归实现反转链表
需要注意三个问题:输入的链表头指针为None或者整个链表只有一个结点时,反转后的链表出现断裂,返回的翻转之后的头节点不是原始链表的尾结点。因此需要引入一个翻转后的头结点,以及一个指向当前结点的指针,一个指向当前结点前一个结点的指针,一个指向当前结点后一个结点的指针,防止出现断裂。
- '''
- 反转链表
- 输入一个链表,反转链表后,输出链表的所有元素
- '''
-
- # -*- coding:utf-8 -*-
- class ListNode:
- def __init__(self, x):
- self.val = x
- self.next = None
- class Solution:
- # 返回ListNode
- def ReverseList(self, pHead):
- pReversedHead = None
- pNode = pHead
- pPrev = None
- while pNode != None:
- pNext = pNode.next
-
- if pNext == None:
- pReversedHead = pNode
-
- pNode.next = pPrev
- pPrev = pNode
- pNode = pNext
- return pReversedHead
- # 递归实现反转链表
- def ReverseListRec(self, pHead):
- if not pHead or not pHead.next:
- return pHead
- else:
- pReversedHead = self.ReverseList(pHead.next)
- pHead.next.next = pHead
- pHead.next = None
- return pReversedHead
-
- node1 = ListNode(10)
- node2 = ListNode(11)
- node3 = ListNode(13)
- node1.next = node2
- node2.next = node3
-
- S = Solution()
- p = S.ReverseList(node1)
- print(p.next.val)
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。