median_search2.cpp

/**
 * @file
 * @brief Given a linked list L[0,....,n] of n numbers, find the middle node.
 *
 * @details The technique utilized in this implementation is the ["Floyd's
 * tortoise and
 * hare"](https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare)
 * approach. This technique uses two pointers that iterate through the list at
 * different 'speeds' in order to solve problems. In this implementation, for
 * every iteration the slow pointer advances one node while the fast pointer
 * advances two nodes. The result of this is that since the fast pointer moves
 * twice as fast as the slow pointer, when the fast pointer reaches the end of
 * the list the slow pointer will be pointing to the middle node of the list.
 *
 * Here are some example lists you can use to see how the algorithm works
 * A = [1,2,3,4,5]
 * B = [1,2,3,4,5,6]
 * print median(A) #should be 39
 * print median(B) #should be 4
 *
 * @author [Benjamin Weiss](https://github.com/weiss-ben)
 * @see median_search.cpp
 */

#include <cassert>   /// for assert
#include <iostream>  /// for IO operations

/**
 * Definition for singly-linked list.
 */
struct ListNode {
    int val{0};               ///< the value stored in the node
    ListNode* next{nullptr};  ///< pointer to the next node
    ListNode() = default;     ///< default constructor
    explicit ListNode(int x)
        : val(x) {}  ///< constructor with value for node->val provided
    ListNode(int x, ListNode* next)
        : val(x),
          next(next) {
    }  ///< constructor with values provided for node->val and node->next
};

/**
 * @namespace search
 * @brief Search algorithms
 */
namespace search {
/**
 * @namespace median_search
 * @brief Functions for the Median Search algorithm implementation. Wkipedia
 * link to algorithm: https://en.wikipedia.org/wiki/Median_search
 */
namespace median_search2 {
/**
 * This function searches for the median of a linked list.
 * @param head The head of the linked list.
 * @returns Median node of the linked list.
 */
ListNode* middleNode(ListNode* head) {
    if (!head) {
        return nullptr;
    }

    // Fast and slow pointers
    ListNode* fastptr = nullptr;
    ListNode* slowptr = fastptr = head;

    // fast jumps 2 while slow jumps 1
    while (fastptr->next && fastptr->next->next) {
        slowptr = slowptr->next;
        fastptr = fastptr->next->next;
    }

    return (fastptr->next) ? slowptr->next : slowptr;
}

void deleteAll(const ListNode* const head) {
    if (head) {
        deleteAll(head->next);
        delete head;
    }
}
}  // namespace median_search2
}  // namespace search

/**
 * @brief Self-test implementations
 * @returns void
 */
static void test() {
    auto* head1 = new ListNode;
    head1->val = 1;

    ListNode* temp = head1;
    for (int i = 2; i < 6; ++i) {
        // Allocate next
        auto* temp1 = new ListNode;
        temp1->val = i;

        // Advance
        temp->next = temp1;
        temp = temp1;
    }
    temp->next = nullptr;

    const ListNode* const median = search::median_search2::middleNode(head1);
    assert(3 == median->val);  // 3 is the value of the median node.
    search::median_search2::deleteAll(head1);
    std::cout << "test case:1 passed\n";

    // Test case # 2
    auto* head2 = new ListNode;
    head2->val = 1;

    ListNode* temp2 = head2;
    for (int i = 2; i < 7; ++i) {
        // Allocate next
        auto* temp3 = new ListNode;
        temp3->val = i;

        // Advance
        temp2->next = temp3;
        temp2 = temp3;
    }
    temp2->next = nullptr;

    const ListNode* const median1 = search::median_search2::middleNode(head2);
    assert(4 == median1->val);  // 4 is the value of the median node.
    search::median_search2::deleteAll(head2);
    std::cout << "test case:2 passed\n";

    std::cout << "--All tests passed--\n";
}

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    test();  // run self-test implementations
    return 0;
}