本题是反转一个单链表,题目提示使用迭代和递归两种方式,属于比较基础的题目。
一,迭代方式:总体思路是从左到右遍历链表结点,依次反转连接关系。每次处理相邻的两个结点,从<None,head>这一对开始。代码如下:
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
prev=None
while head:
next = head.next
head.next=prev
prev = head
head = next
return prev
代码中prev为每次结点对的先序结点,当head为None时,prev为目前链表的末结点,所以返回prev. 注意每次需要反转一个连接,所以每次的节点对之间有一个节点的重合.另外头节点的next一定要置为0,不然会形成回环.
二,递归方式,假设前面已经反转,现在这一步要怎么处理。一定要掌握,被腾讯问到。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
return self.helper(None, head)
def helper(self, pre, cur):
if not cur:
return pre
next = cur.next #the next cur node
cur.next = pre # cur is the next pre node
return self.helper(cur, next)
转载于:https://www.cnblogs.com/sherylwang/p/5393439.html
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)