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;
}

Complexity Analysis

The time complexity for this 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.