Reverse Linked List

Problem Statement

LeetCode-206: Given the head of a singly linked list, reverse the list, and return the reversed list.

Approach

For each node, we need to reverse the pointer to the previous node. We also need to keep track of the next node to avoid losing the reference to the next node.

1. Initialize prev to null.
2. Iterate over the linked list.
3. Store the next node in a temporary variable.
4. Reverse the pointer of the current node to the previous node.
5. Update the previous node to the current node.
6. Update the current node to the next node.
7. Return the previous node as the new head of the reversed linked list.

Implementation

public ListNode reverseList(ListNode head) {
    ListNode prev = null;

    while(null != head){
        ListNode temp = head.next;
        head.next = prev;
        prev = head;
        head = temp;
    }   
    return prev;
}

Follow-up

Can we solve this problem using recursion?

The recursive approach is similar to the iterative approach:

1. Traverse the linked list recursively until the end.
2. Reverse the next reference of the next node to the current node.
3. Reset the next reference of the current node to null.
4. Return the new head of the reversed linked list.

public ListNode reverseList(ListNode head) {
    if(null == head || null == head.next){
        return head;
    }
    // new head of the reversed linked list
    ListNode temp = reverseList(head.next);
    // reverse the next reference of next node to current node
    // reset the next reference of current node to null
    head.next.next = head;
    head.next = null;
    return temp;
}

Complexity Analysis

The time complexity for iterative approach is \(O(n)\) as we are iterating over the linked list once. The space complexity is \(O(1)\) as we are using a constant amount of space for storing the temporary reference.

The time complexity for the recursive approach is \(O(n)\) as we are traversing the linked list once. Additionally, the associated space complexity is \(O(n)\) due to the recursive stack.