median_search2.cpp File Reference

Given a linked list L[0,....,n] of n numbers, find the middle node. More...

#include <cassert>
#include <iostream>

Include dependency graph for median_search2.cpp:

Go to the source code of this file.

Classes
struct	ListNode
	for IO operations More...

Namespaces
namespace	search
	for std::assert
namespace	median_search
	Functions for Median search algorithm.

Functions
ListNode *	search::median_search2::middleNode (ListNode *head)
void	search::median_search2::deleteAll (const ListNode *const head)
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Given a linked list L[0,....,n] of n numbers, find the middle node.

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

See also

median_search.cpp

Definition in file median_search2.cpp.

Function Documentation

deleteAll()

void search::median_search2::deleteAll

(

const ListNode *const

head

)

Definition at line 77 of file median_search2.cpp.

                                           {
    if (head) {
        deleteAll(head->next);
        delete head;
    }
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 139 of file median_search2.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

middleNode()

ListNode * search::median_search2::middleNode

(

ListNode *

head

)

This function searches for the median of a linked list.

Parameters

head	The head of the linked list.

Returns

Median node of the linked list.

Definition at line 59 of file median_search2.cpp.

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

test()

static void test ( )

static

Self-test implementations.

Returns

void

Definition at line 90 of file median_search2.cpp.

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