Reverse Linked List - Leetcode Solution

The Reverse Linked List problem on LeetCode is a popular problem that involves reversing the order of a singly linked list. This problem is rated as "Easy" difficulty on the LeetCode website and is a great problem for beginners to practice with.

The problem statement is as follows:

"Reverse a singly linked list."

Example:

Input: 1->2->3->4->5->NULL

Output: 5->4->3->2->1->NULL

To solve this problem, we can use the iterative or the recursive approach. However, the iterative approach is more efficient and faster.

Iterative Solution

In the iterative solution, we need to traverse the linked list from the beginning and keep reversing the pointers until we reach the end of the list. We can maintain three pointers while traversing the list - current node, previous node, and next node.

Algorithm:

1. Initialize previous node to NULL, current node to head, and next node to NULL.
2. Traverse the linked list with the help of the current node.
3. At each iteration, assign current->next = previous.
4. Move to the next node with the help of the next pointer.
5. Update previous node to the current node.
6. Continue traversing the linked list until the current node is NULL.
7. Return the new head, which is the previous node.

Code:

ListNode* reverseList(ListNode* head) {
    ListNode *prev = NULL, *current = head, *next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

Time Complexity: O(n)

Space Complexity: O(1)

The above implementation takes O(n) time complexity, where n is the number of nodes in the linked list. The space complexity of the algorithm is O(1).

Recursive Solution

In the recursive solution, we reverse the list from the current node to the end of the list. Once we reach the end of the list, we update the pointer of the previous node to the current node.

Algorithm:

1. If head is NULL or the list is empty, return head.
2. Recursively reverse the rest of the list from the next node.
3. Once we reach the end of the list, update the pointer for the previous node to the current node.
4. Return the new head, which is the current node.

Code:

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

Time Complexity: O(n)

Space Complexity: O(n)

The above implementation takes O(n) time complexity, where n is the number of nodes in the linked list. The space complexity of the algorithm is O(n) because we are using recursion. Each recursive call adds a new call frame to the call stack, which takes up space. This can lead to a stack overflow error for large input sizes.

Conclusion:

In conclusion, the Reverse Linked List problem is a great practice problem for beginners to get started with linked lists. The iterative solution is more efficient and faster since it has a space complexity of O(1). However, the recursive solution is also a good implementation to understand the concept of recursion.

1