Reverse Linked List

Difficulty: Easy | Acceptance: 80.50% | Paid: No Topics: Linked List, Recursion

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

Examples
Constraints
Iterative Approach
Recursive Approach

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints

The number of nodes in the list is in the range [0, 5000].
-5000 <= Node.val <= 5000

Iterative Approach

Intuition Traverse the linked list once, reversing the direction of the next pointer for each node as we go.

Steps

Initialize two pointers, prev and curr, pointing to null and head respectively.
Iterate while curr is not null:
- Save the next node of curr.
- Point curr.next to prev.
- Move prev to curr.
- Move curr to the saved next node.
Return prev as the new head of the reversed list.

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -&gt; ListNode:
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev

Complexity

Time: O(n)
Space: O(1)
Notes: Most optimal solution for space complexity.

Recursive Approach

Intuition Recursively reverse the sublist starting from the next node, then make the next node point back to the current node.

Steps

Base case: if head is null or head.next is null, return head.
Recursively call reverseList on head.next and store the result as new_head.
Set head.next.next to head to reverse the link.
Set head.next to null to break the old forward link.
Return new_head.

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -&gt; ListNode:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Complexity

Time: O(n)
Space: O(n)
Notes: Uses stack space proportional to the length of the list.