Overview

Problem 1: Find the Middle of a Linked List

Problem Statement:

Given a singly linked list, find the middle node.

Solution:

To find the middle of a linked list, you can use the slow and fast pointers again. Move the slow pointer one step at a time and the fast pointer two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

Time Complexity: O(n)

Space Complexity: O(1)

Node* findMiddle(Node* head) {
    Node* slow = head;
    Node* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;  // Middle node
}

Problem 2: Reverse a Single Linked List

Problem Statement: Given a singly linked list, reverse the list in-place.

Solution:

To reverse a single linked list, we can iterate through the list while maintaining pointers to the current node, the next node, and the previous node. We update the next pointers to reverse the list. Here's the code:

Node* reverseLinkedList(Node* head) {
    Node* current = head;
    Node* prev = nullptr;
    
    while (current != nullptr) {
        Node* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    return prev;  // New head of the reversed list
}

Problem 3: Detect a Loop in a Linked List

Problem Statement: Given a singly linked list, determine if it contains a loop.

Solution:

You can solve this problem using Floyd's cycle-finding algorithm. Maintain two pointers: one slow pointer (moves one step at a time) and one fast pointer (moves two steps at a time). If there's a loop, the fast pointer will eventually catch up to the slow pointer.

bool hasLoop(Node* head) {
    Node* slow = head;
    Node* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return true;  // Loop detected
        }
    }

    return false;  // No loop
}

Problem 4: Find the Nth Node from the End of a Linked List

Problem Statement: Given a singly linked list, find the Nth node from the end of the list. You cannot count the nodes or use extra memory.

Solution:

To solve this problem, you can use two pointers. Initialize one pointer at the head and move the other pointer N nodes ahead. Then, move both pointers one node at a time until the second pointer reaches the end of the list.

Node* findNthFromEnd(Node* head, int n) {
    Node* first = head;
    Node* second = head;
    
    // Move the second pointer n nodes ahead
    for (int i = 0; i < n; i++) {
        if (second == nullptr) {
            // Handle cases where n is greater than the list length
            return nullptr;
        }
        second = second->next;
    }
    
    // Move both pointers one node at a time
    while (second != nullptr) {
        first = first->next;
        second = second->next;
    }
    
    return first;  // Nth node from the end
}