Reverse linked list#

Levels: level-1

Data structures: linkedlist

Practice Link#

Description#

Reverse a singly linked list.

Example#

1Input: 1->2->3->4->5->NULL
2Output: 5->4->3->2->1->NULL

Follow up#

A linked list can be reversed either iteratively or recursively. Could you implement both?

Python Solution#

 1class ListNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.next = None
 5
 6
 7class Solution(object):
 8    def reverseList(self, head):  # Iterative
 9        prev, curr = None, head
10        while curr:
11            curr.next, prev, curr = prev, curr, curr.next
12        return prev
13
14    def reverseList_v1(self, head):  # Recursive
15        """
16        :type head: ListNode
17        :rtype: ListNode
18        """
19        if not head or not head.next:
20            return head
21        p = self.reverseList_v1(head.next)
22        head.next.next = head
23        head.next = None
24        return p