Easy

Reverse Linked List

022

Given a linked list encoded as an array, return the values in reversed linked-list order.

EXAMPLES

Example 1

Input
{
  "head": [
    1,
    2,
    3,
    4,
    5
  ]
}

Output
[
  5,
  4,
  3,
  2,
  1
]

FUNCTION SHAPE

head: intArray→intArray

SOLUTION NOTE

To understand this, let's visualize the reversal process:

Initial state:

textEXAMPLE

None ← prev | current → [1] → [2] → [3] → None

First iteration:

textEXAMPLE

None ← [1] ← prev | current → [2] → [3] → None

Second iteration:

textEXAMPLE

None ← [1] ← [2] ← prev | current → [3] → None

Final state:

textEXAMPLE

None ← [1] ← [2] ← [3] ← prev | current → None

For the recursive case: just draw it out.

1 -> 2 -> 3

We have 1 and 3 -> 2.

We want to set 2 -> 1. However we only have access to the 1 and 3 right now. Iterating from one end of 3 to 2 will take O(n) time, which makes the recursion O(n^2).

But know that 1.next is STILL 2…
So we can access 2 through head.next, and we want to set head.next.next = head.
Now, we just need to get rid of 1 -> 2, by setting head.next = None. so now we have 3 -> 2 -> 1 -> None!

Reveal reference solution +

pythonREFERENCE

# Iterative solution
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

# Recursive solution
def reverseListRecursive(self, head: ListNode) -> ListNode:
    # Base case: empty list or list with only one node
    if not head or not head.next:
        return head

    # Recursively reverse the rest of the list after head
    new_head = self.reverseListRecursive(head.next)

    # The node after head now points back to head
    head.next.next = head

    # Head becomes the new tail, so it points to None
    head.next = None

    # Return the new head of the reversed list
    return new_head

TimeO(n)

SpaceO(1) iterative, O(n) recursive

Open on LeetCode ↗