-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlistloop.cpp
More file actions
127 lines (100 loc) · 3.15 KB
/
Copy pathlistloop.cpp
File metadata and controls
127 lines (100 loc) · 3.15 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
template <typename T>
class list_node
{
public:
list_node( T data ) : data( data ), next( NULL ) {}
list_node( T data, list_node<T> *next ) : data( data ), next( next) {}
T data;
list_node<T> *next;
};
template <typename T>
class linked_list
{
public:
linked_list() : head( NULL ) {}
list_node<T> *head;
void push_front( T data );
void push_back( T data );
std::pair<list_node<T>*, list_node<T>*> find_loop();
private:
bool points_back( list_node<T> *first, list_node<T> *second );
};
template <typename T>
void linked_list<T>::push_front( T data )
{
head = new list_node<T>( data, head );
}
template <typename T>
void linked_list<T>::push_back( T data )
{
if( head == NULL ) return push_front( data );
list_node<T> *new_node = new list_node<T>( data );
list_node<T> *node = head;
while( node->next != NULL ) node = node->next;
node->next = new_node;
}
/* return a pair of nodes, the second pointing back to the first, which
* is earlier in the list. */
template <typename T>
std::pair<list_node<T>*, list_node<T>*> linked_list<T>::find_loop()
{
std::pair<list_node<T>*, list_node<T>*> result( NULL, NULL );
if( head == NULL ) return result;
list_node<T> *slow = head;
list_node<T> *fast = head;
bool increment_slow = false;
int loops = 0;
while( true )
{
++loops;
if( fast == NULL )
{
std::cout << "result found in " << loops << " loops" << std::endl;
return result;
}
if( fast->next == slow )
{
result.first = slow;
result.second = fast;
std::cout << "result found in " << loops << " loops" << std::endl;
return result;
}
fast = fast->next;
if( increment_slow )
{
increment_slow = !increment_slow;
slow = slow->next;
}
}
return result;
}
template <typename T>
bool linked_list<T>::points_back( list_node<T> *first, list_node<T> *second )
{
if( second == first ) return false;
if( second->next == first ) return true;
if( second->next == NULL ) return false;
return points_back( first->next, second );
}
int main()
{
linked_list<int> list;
for( int i = 0; i < 20; ++i ) list.push_front( i );
list_node<int> *node = list.head;
while( node->next != NULL ) node = node->next;
// create loop
node->next = list.head;
auto loop_result = list.find_loop();
if( loop_result.first != NULL )
std::cout << "list has loop; node with data " << loop_result.second->data << " points back to node with data " << loop_result.first->data << std::endl;
else
std::cout << "list has no loop" << std::endl;
linked_list<int> no_loop;
for( int i = 0; i < 20; ++i ) no_loop.push_front( i );
loop_result = no_loop.find_loop();
if( loop_result.first != NULL )
std::cout << "list has loop; node with data " << loop_result.second->data << " points back to node with data " << loop_result.first->data << std::endl;
else
std::cout << "list has no loop" << std::endl;
}