206. Reverse Linked List
Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution: Iterative
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre, cur = cur, nxt
return pre
Solution: Recursive
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def reverse(node):
if not node:
dummy = ListNode(None)
return dummy, dummy
nxt, dummy = reverse(node.next)
nxt.next = node
node.next = None
return node, dummy
return reverse(head)[1].next