206. Reverse Linked List

Easy

Problem:

Reverse the linked list.

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

https://leetcode.com/problems/reverse-linked-list/

Solution:

Revursive 🔥

During the recursion, you keep attaching the previous list (prev) to node.next until node becomes None. When that happens, the linked list gets connected in reverse order due to backtracking. The prev that is returned first ends up being the first node of the reversed linked list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node: ListNode, prev: ListNode = None):
            if not node:
                return prev
            next, node.next = node.next, prev
            return reverse(next, node)
        return reverse(head)

Here is an explanation of the recursive function:

Let's take an example to clarify this. Suppose we have a linked list 1 -> 2 -> 3 -> 4 -> 5 and we want to reverse it:

1. Initially, head points to 1, prev is None. After executing next, node.next = node.next, prev, next points to 2 and node.next (1's next) points to None (as it is reversed). Now 1 -> None and next is 2.

2. We then call reverse(next, node) which is reverse(2, 1).

3. In this call, node is 2, prev is 1. After executing next, node.next = node.next, prev, next points to 3 and node.next (2's next) points to 1 (as it is reversed). Now our list looks like: 2 -> 1 -> None and next is 3.

4. The process continues until we have traversed all the elements in the list.

After all calls, the list will be reversed as 5 -> 4 -> 3 -> 2 -> 1 -> None, and the head of the new list (5) will be returned.

Iterative

Iteration takes about 70% less memory than recursion, which means it has a lower space complexity. Despite this, iteration tends to run slightly faster.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node, prev = head, None
        
        while node:
            next, node.next = node.next, prev
            prev, node = node, next

        return prev