Repository: TheAlgorithms/C-Plus-Plus
File: search/median_search2.cpp (C++)

Code before:
 *
 * @author [Benjamin Weiss](https://github.com/weiss-ben)
 */

/**
 * Definition for singly-linked list.
 */
struct ListNode {
    int val;												// The value stored in the node
    ListNode *next;											// Pointer to the next node
    ListNode() : val(0), next(nullptr) {}					// Default constructor
    ListNode(int x) : val(x), next(nullptr) {}				// 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
 };
 
 #include <iostream> /// for IO operations
 #include <cassert>  /// for assert

/**
 * @namespace search
 * @brief Search algorithms
 */
namespace search {
/**
 * @namespace median_search
 * @brief Functions for the Median Search algorithm implementation.
 */
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;
    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;
        
}
}  // namespace median_search2
}  // namespace search

Review comment (performance):
Could you please provide a Wikipedia link to the Median Search algorithm?


__
[![sema-logo](https://app.semasoftware.com/img/sema-tray-logo.gif)](https://semasoftware.com/gh) &nbsp;**Summary:** :hammer_and_wrench: This code needs a fix&nbsp; | &nbsp;**Tags:** Inefficient


Code after:
 * 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;