Questions¶
Difficulty: Easy
Reverse a singly linked list.
Hint
- A linked list can be reversed either iteratively or recursively. Could you implement both?
Coding¶
python-1¶
# -*- coding: utf-8 -*-
# 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
"""
if head is None or head.next is None:
return head
pre, p, next = head, head, None
while p != None:
pre, p.next, next = p, pre, p.next
# next = p.next
# p.next = pre
# pre = p
p = next
head.next = None
return pre
python-2¶
# -*- coding: utf-8 -*-
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverse(self, p):
if p.next is None:
return p
else:
next = p.next
tail = self.reverse(next)
next.next = p
return tail
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None or head.next is None:
return head
else:
tail = self.reverse(head)
head.next = None
return tail