206. Reverse Linked List

🟩 Easy

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

Example 1

list

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

Example 2

list

Input: head = [1,2] Output: [2,1]

Example 3

Input: head = [] Output: []

Constraints

• The number of nodes in the list is the range [0, 5000].

• -5000 <= Node.val <= 5000

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

Solution

My Solution (Iterative)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var (
        prev, curr, next *ListNode
    )
    curr = head

    for curr != nil {
        next = curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    return prev
}

Optimal Solution (Recursive)

func reverseList(head *ListNode) *ListNode {
    // Base case: empty list or single node
    if head == nil || head.Next == nil {
        return head
    }
    
    // Recursively reverse the rest of the list
    rest := reverseList(head.Next)
    
    // Fix the connections
    head.Next.Next = head
    head.Next = nil
    
    return rest
}

Approach Analysis

This classic problem can be solved in two main ways:

1. Iterative Approach (Your Solution):

   • Uses three pointers for explicit control

   • Reverses links one by one

   • Very space efficient

   • Great for interviews

2. Recursive Approach (Optimal):

   • Elegant divide-and-conquer

   • Reverses from back to front

   • More mathematical

   • Cleaner code

Visualization of Both Approaches

Iterative Process

Initial: 1 -> 2 -> 3 -> 4 -> 5
Step 1:  nil <- 1    2 -> 3 -> 4 -> 5
Step 2:  nil <- 1 <- 2    3 -> 4 -> 5
Final:  nil <- 1 <- 2 <- 3 <- 4 <- 5

Recursive Process

Initial Call Stack:
reverseList(1->2->3->4->5)
  reverseList(2->3->4->5)
    reverseList(3->4->5)
      reverseList(4->5)
        reverseList(5)
          return 5

Unwinding:
5 is new head
4->5->4 becomes 5->4
3->4 becomes 4->3
2->3 becomes 3->2
1->2 becomes 2->1

Complexity Analysis

Iterative Solution

• Time: O(n)

  • Single pass through list

  • Constant work per node

  • No repeated work

• Space: O(1)

  • Only three pointers

  • Constant extra space

  • True in-place reversal

Recursive Solution

• Time: O(n)

  • Visits each node once

  • Constant work per node

  • Same as iterative

• Space: O(n)

  • Recursive call stack

  • One frame per node

  • Not truly in-place

Why Both Solutions Work

1. Iterative Approach:

   • Maintains clear invariants

   • Never loses track of nodes

   • Very mechanical process

   • Easy to visualize

2. Recursive Approach:

   • Assumes subproblem solved

   • Works backwards elegantly

   • More mathematical thinking

   • Cleaner implementation

When to Use Each

1. Choose Iterative When:

   • Memory is constrained

   • Large input expected

   • Maximum performance needed

   • Interview setting

2. Choose Recursive When:

   • Code clarity priority

   • Small to medium input

   • Teaching/learning

   • Quick implementation needed

Common Patterns & Applications

1. Similar Problems:

   • Reverse Linked List II

   • Palindrome Linked List

   • Swap Nodes in Pairs

2. Key Techniques:

   • Multiple pointer manipulation

   • Recursion on linked structure

   • Link reversal

   • Stack usage (implicit/explicit)

Interview Tips

1. Discuss Both Approaches:

   • Mention space trade-offs

   • Explain time complexity

   • Discuss pros and cons

   • Show knowledge depth

2. Common Pitfalls:

   • Not saving next pointer

   • Stack overflow in recursion

   • Infinite loops

   • Lost references

3. Testing Strategy:

   • Empty list

   • Single node

   • Two nodes

   • General case

   • Check all links

result

Leetcode: link