206. Reverse Linked List - Explanation

Problem Link

Description

Given the beginning of a singly linked list head, reverse the list, and return the new beginning of the list.

Example 1:

Input: head = [0,1,2,3]

Output: [3,2,1,0]

Example 2:

Input: head = []

Output: []

Constraints:

  • 0 <= The length of the list <= 1000.
  • -1000 <= Node.val <= 1000


Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.


Hint 1

A brute force solution would be to store the node values of the linked list into an array, then reverse the array, convert it back into a linked list, and return the new linked list's head. This would be an O(n) time solution but uses extra space. Can you think of a better way? Maybe there is an approach to reverse a linked list in place.


Hint 2

As you can see, the head of the linked list becomes the tail after we reverse it. Can you think of an approach to change the references of the node pointers? Perhaps reversing a simple two-node list might help clarify the process.


Hint 3

For example, consider a list [2, 3], where 2 is the head of the list and 3 is the tail. When we reverse it, 3 becomes the new head, and its next pointer will point to 2. Then, 2's next pointer will point to null. Can you figure out how to apply this approach to reverse a linked list of length n by iterating through it?


Hint 4

We can reverse the linked list in place by reversing the pointers between two nodes while keeping track of the next node's address. Before changing the next pointer of the current node, we must store the next node to ensure we don't lose the rest of the list during the reversal. This way, we can safely update the links between the previous and current nodes.


Company Tags

Google10 Amazon8 Bloomberg5 Apple4 Meta3 Microsoft3 Goldman Sachs3 NVIDIA2 Visa2 Qualcomm2 Oracle12 Yahoo8 Adobe7 Tiktok7 TCS4 Yandex4 Cisco3 Siemenes3 ServiceNow3 SAP3


1. Recursion

Intuition

Reversing a linked list using recursion works by thinking in terms of “reverse the rest, then fix the pointer for the current node.”
When we recursively go to the end of the list, that last node becomes the new head.
While the recursion unwinds, each node points backward to the one that called it.
Finally, we set the original head’s next to None to finish the reversal.

This approach uses the call stack to naturally reverse the direction of the pointers.

Algorithm

  1. If the list is empty, return None.
  2. Recursively call the function on head.next to reverse the rest of the list.
  3. After the recursive call returns:
    • Make head.next.next = head so the next node points back to the current node.
  4. Set head.next = None to avoid cycles.
  5. Return the new head returned by the deepest recursive call.
# 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]:
        if not head:
            return None

        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head
        head.next = None

        return newHead

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

2. Iteration

Intuition

Reversing a linked list iteratively is all about flipping pointers one step at a time.
We walk through the list from left to right, and for each node, we redirect its next pointer to point to the node behind it.

To avoid losing track of the rest of the list, we keep three pointers:

  • curr → the current node we are processing
  • prev → the node that should come after curr once reversed
  • temp → the original next node (so we don’t break the chain)

By moving these pointers forward in each step, we gradually reverse the entire list.
When curr becomes None, the list is fully reversed, and prev points to the new head.

Algorithm

  1. Initialize:
    • prev = None
    • curr = head
  2. While curr exists:
    • Save the next node: temp = curr.next
    • Reverse the pointer: curr.next = prev
    • Move prev to curr
    • Move curr to temp
  3. When the loop ends, prev is the new head of the reversed list.
  4. Return prev.
# 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: ListNode) -> ListNode:
        prev, curr = None, head

        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)