Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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:

Classes

struct  ListNode
 for IO operations More...
 

Namespaces

namespace  search
 for std::vector
 
namespace  median_search
 

Functions

ListNodesearch::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

Function Documentation

◆ deleteAll()

void search::median_search2::deleteAll ( const ListNode *const head)
77 {
78 if (head) {
79 deleteAll(head->next);
80 delete head;
81 }
82}

◆ main()

int main ( void )

Main function.

Returns
0 on exit
139 {
140 test(); // run self-test implementations
141 return 0;
142}
static void test()
Self-test implementations.
Definition median_search2.cpp:90
Here is the call graph for this function:

◆ middleNode()

ListNode * search::median_search2::middleNode ( ListNode * head)

This function searches for the median of a linked list.

Parameters
headThe head of the linked list.
Returns
Median node of the linked list.
59 {
60 if (!head) {
61 return nullptr;
62 }
63
64 // Fast and slow pointers
65 ListNode* fastptr = nullptr;
66 ListNode* slowptr = fastptr = head;
67
68 // fast jumps 2 while slow jumps 1
69 while (fastptr->next && fastptr->next->next) {
70 slowptr = slowptr->next;
71 fastptr = fastptr->next->next;
72 }
73
74 return (fastptr->next) ? slowptr->next : slowptr;
75}
for IO operations
Definition median_search2.cpp:31
ListNode * next
pointer to the next node
Definition median_search2.cpp:33
Here is the call graph for this function:

◆ test()

static void test ( )
static

Self-test implementations.

Returns
void
90 {
91 auto* head1 = new ListNode;
92 head1->val = 1;
93
94 ListNode* temp = head1;
95 for (int i = 2; i < 6; ++i) {
96 // Allocate next
97 auto* temp1 = new ListNode;
98 temp1->val = i;
99
100 // Advance
101 temp->next = temp1;
102 temp = temp1;
103 }
104 temp->next = nullptr;
105
107 assert(3 == median->val); // 3 is the value of the median node.
108 search::median_search2::deleteAll(head1);
109 std::cout << "test case:1 passed\n";
110
111 // Test case # 2
112 auto* head2 = new ListNode;
113 head2->val = 1;
114
115 ListNode* temp2 = head2;
116 for (int i = 2; i < 7; ++i) {
117 // Allocate next
118 auto* temp3 = new ListNode;
119 temp3->val = i;
120
121 // Advance
122 temp2->next = temp3;
123 temp2 = temp3;
124 }
125 temp2->next = nullptr;
126
128 assert(4 == median1->val); // 4 is the value of the median node.
129 search::median_search2::deleteAll(head2);
130 std::cout << "test case:2 passed\n";
131
132 std::cout << "--All tests passed--\n";
133}
ListNode * middleNode(ListNode *head)
Definition median_search2.cpp:59
int val
the value stored in the node
Definition median_search2.cpp:32