#206

Easy

LeetCode Problem Workspace

Reverse Linked List

Reverse a singly linked list in place, converting the head to tail, with an iterative or recursive approach.

Problem Statement

Given the head of a singly linked list, reverse the list in place, updating the next pointers of each node so that the original tail becomes the new head. You must return the new head after the reversal.

The reversal should be done in place, meaning no extra space is used for a new list. After reversal, the original head becomes the tail of the list. Consider the edge case where the list is empty or consists of a single node.

Examples

Example 1

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

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

Each node's next pointer is flipped so the original tail becomes the new head.

Example 2

Input: head = []

Output: []

An empty list stays empty. This is a useful edge case to call out before coding.

Constraints

0 <= number of nodes <= 5000
-5000 <= Node.val <= 5000
The list is singly linked, so each node only points forward in the original input.
Returning the new head is required because the original head becomes the tail.

Solution Approach

Iterative Approach

In the iterative approach, use three pointers: previous, current, and next. Start with previous as null, current as the head, and next as null. Traverse the list, at each step, reverse the direction of the current node’s pointer. This approach has O(n) time complexity and uses O(1) space because it only updates pointers without needing extra data structures.

Recursive Approach

The recursive approach also reverses the list by reaching the end first and then reversing the pointer direction as the recursion unwinds. The base case is when the current node is null or the next node is null. This method has O(n) time complexity but uses O(n) space due to the function call stack.

Edge Cases

Consider the edge case of an empty list or a single-node list. These should return the list as-is. It's essential to handle these cases without additional computation to avoid unnecessary operations.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1) for the iterative solution

The iterative solution runs in O(n) time because each node is visited once. It uses O(1) space since it only requires a few pointer variables. The recursive approach also runs in O(n) time but uses O(n) space because of recursion stack frames for each node.

What Interviewers Usually Probe

Do you know how to handle pointer updates safely without losing references to nodes?
Can you explain the difference in space complexity between the iterative and recursive solutions?
Are you familiar with edge cases such as empty lists or lists with only one element?

Common Pitfalls or Variants

Common pitfalls

Failing to maintain the correct order of nodes during pointer reversal, leading to lost references.
Overcomplicating the solution with extra data structures, which isn't needed for in-place reversal.
Forgetting to handle the case where the list is empty or has only one node.

Follow-up variants

Reverse a doubly linked list in place.
Reverse a linked list in groups of k nodes.
Reverse a linked list in a more memory-efficient way using tail recursion.

FAQ

How can I reverse a linked list iteratively?

You can reverse the list iteratively by using three pointers: previous, current, and next. Traverse the list, updating each node's next pointer.

What is the time complexity of reversing a linked list?

Reversing the list takes O(n) time, where n is the number of nodes, because each node is visited once.

Why is the recursive solution slower than the iterative one?

The recursive solution has the same time complexity as the iterative one, but it uses additional memory due to the function call stack.

How do I handle an empty list in this problem?

If the list is empty, simply return the head as null without performing any reversal, as there's nothing to reverse.

What is the iterative method's advantage over the recursive one?

The iterative method uses constant space (O(1)), making it more memory-efficient compared to the recursive method, which uses O(n) space.

terminal

Solution

Solution 1: Head Insertion Method

We create a dummy node $\textit{dummy}$, then traverse the linked list and insert each node after the $\textit{dummy}$ node. After traversal, return $\textit{dummy.next}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# 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:
        dummy = ListNode()
        curr = head
        while curr:
            next = curr.next
            curr.next = dummy.next
            dummy.next = curr
            curr = next
        return dummy.next

Solution 2: Recursion

We recursively reverse all nodes from the second node to the end of the list, then attach the $head$ to the end of the reversed list.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# 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:
        dummy = ListNode()
        curr = head
        while curr:
            next = curr.next
            curr.next = dummy.next
            dummy.next = curr
            curr = next
        return dummy.next

Continue Practicing

#1 two sum #207 course schedule