Reverse Linked List

Thought Process

To reverse a linked list, we can either use a recursive approach or an iterative approach:

Approach 1: Recursive Approach - Base case: If the list is empty or has only one node, return the head else recursively reverse the rest of the list and adjust the pointers to reverse the current node. Finally, return the new head of the reversed list.

Approach 2: Iterative Approach - Use three pointers: prev, curr, and tmp. Traverse the list, adjusting the next pointers to reverse the direction of the list. Finally, return the new head of the reversed list.

Approach 1: Recursive Approach

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        if(head==null || head.next == null)
            return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Approach 2: Iterative Approach

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode prev = null;
        ListNode curr = head;

        while(curr!=null){

            ListNode future = curr.next;
            curr.next = prev;
            prev = curr;
            curr = future;
        }
        return prev;
    }
}

Code Complexity

Time Complexity: O(n)

Both approaches iterate through the list once, making them linear in time complexity.

Space Complexity: O(1) or O(n)

The iterative approach uses constant space, while the recursive approach uses stack space proportional to the length of the list.