LeetCode 206: Reverse Linked List

Explanation

To reverse a linked list, we can iterate through the list while reversing the pointers to point in the opposite direction. We need to keep track of the current node, the next node, and the previous node to perform the reversal.

1. Iterative Approach:

   • Initialize three pointers: prev as null, curr as the head of the list, and next as null.
   • Traverse the list while updating the pointers: set next to curr.next, point curr.next to prev, move prev to curr, and move curr to next.
   • Return prev as the new head of the reversed list.

2. Recursive Approach:

   • The base case is when the current node is null or the next node is null, return the current node.
   • Recursively call the function on the next node, then reverse the pointers by setting curr.next.next to curr and set curr.next to null.
   • Return the new head of the reversed list.

• Time Complexity: O(n) where n is the number of nodes in the linked list.
• Space Complexity: O(1) for the iterative approach and O(n) for the recursive approach due to the stack space used in recursion.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;
        
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}