Reverse Linked List

Given the head of a singly linked list, reverse the list in-place and return the new head of the reversed linked list.

Example:

Input:

Linked List: 1 -> 2 -> 3 -> 4 -> 5

Output:

Reversed Linked List: 5 -> 4 -> 3 -> 2 -> 1

Reverse Linked List Solution in C++:

#include <iostream>

// Definition for singly-linked list
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to reverse a linked list
ListNode* reverseLinkedList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr != nullptr) {
        ListNode* nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }

    return prev; // New head of the reversed linked list
}

int main() {
    // Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    std::cout << "Original Linked List: ";
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;

    ListNode* reversedHead = reverseLinkedList(head);

    std::cout << "Reversed Linked List: ";
    current = reversedHead;
    while (current != nullptr) {
        std::cout << current->val << " -> ";
        current = current->next;
    }
    std::cout << "nullptr" << std::endl;

    return 0;
}

Explanation:

1. The reverseLinkedList function takes the head of the linked list as input and returns the new head of the reversed linked list.
2. We use three pointers, prev, curr, and nextNode, to reverse the linked list in-place.
3. We start with prev set to nullptr and curr set to the head of the linked list.
4. In each iteration of the while loop, we do the following steps:
   a. Store the next pointer of the current node (curr->next) in the nextNode pointer.
   b. Point the next pointer of the current node to the previous node (curr->next = prev), effectively reversing the link.
   c. Move prev to the current node (prev = curr) and curr to the next node (curr = nextNode).
5. When we reach the end of the linked list (curr == nullptr), the prev pointer will be pointing to the last node of the original list, which is the new head of the reversed linked list.

Time Complexity:

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. We visit each node once during the traversal and perform constant-time operations.

Space Complexity:

The space complexity of this solution is O(1) as we are using a constant amount of additional space for the prev, curr, and nextNode pointers. The reversal is done in-place without using any additional data structures.