Split Singly Circular Linked List | C++ Implementation
Given a Singly Circular Linked List, we have to split it into two equal halves. If the number of nodes in the given list is odd then first list will have one node more than the second list.
1
2
3
Input : { 2, 3, 18, 25, 5 }
Output List 1 : { 2, 3, 18 }
Output List 2 : { 25, 5 }
Here is a meme to understand Circular Linked List
From the above fig. first we have to find middle node of the given singly circular linked list.
Middle node can be found using slow_ptr
and fast_ptr
. slow_ptr
increments by one node whereas fast_ptr
increments by two nodes. When fast_ptr->next == head
or fast_pr->next->next == head
then no increment of fast_ptr
or slow_ptr
and slow_ptr
is at the middle node of the list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Node *find_middle_node()
{
//slow pointer advances by 1
Node *slow_ptr = head;
//fast pointer advances by 2
Node *fast_ptr = head;
//If odd number of nodes then fast_ptr->next = head
//If even number of nodes then fast_ptr->next->next = head
while(fast_ptr->next != head && fast_ptr->next->next != head)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
return slow_ptr;
}
After getting middle node, the node next to middle node is the head of second ouput list. Then tail of the lists are updated so that circular list is maintained.
1
2
3
4
5
6
7
8
9
10
void split_list(circular_linked_list<T>& second_half)
{
Node *tail = find_tail_node();
Node *mid = find_middle_node();
second_half.head = mid->next;
tail->next = second_half.head;
mid->next = head;
}
C++ Implementation to Split Circular Linked List
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <iostream>
#include <utility>
template <class T>
class circular_linked_list
{
struct Node
{
T data;
Node * next;
Node(T&& value) : data(std::move(value)), next(nullptr) {}
};
Node *head;
public:
circular_linked_list() : head(nullptr) {}
//copy constructor
circular_linked_list(const circular_linked_list& cll) = delete;
//move constructor
circular_linked_list(circular_linked_list&& cll) = delete;
//copy assignment
circular_linked_list& operator=(const circular_linked_list& cll) = delete;
//move assignment
circular_linked_list& operator=(circular_linked_list&& cll) = delete;
~circular_linked_list();
void insert_node(T&&);
void split_list(circular_linked_list<T>&);
void print_list();
private:
Node *find_tail_node()
{
Node *tmp = head;
while(tmp->next != head)
{
tmp = tmp->next;
}
return tmp;
}
Node *find_middle_node()
{
//slow pointer advances by 1
Node *slow_ptr = head;
//fast pointer advances by 2
Node *fast_ptr = head;
//If odd number of nodes then fast_ptr->next = head
//If even number of nodes then fast_ptr->next->next = head
while(fast_ptr->next != head && fast_ptr->next->next != head)
{
fast_ptr = fast_ptr->next->next;
slow_ptr = slow_ptr->next;
}
return slow_ptr;
}
};
template <class T>
void circular_linked_list<T>::insert_node(T&& value)
{
Node *node = new Node(std::move(value));
if(head == nullptr)
{
node->next = node;
head = node;
return;
}
Node *tmp = head;
while(tmp->next != head)
{
tmp = tmp->next;
}
tmp->next = node;
node->next = head;
}
template <class T>
void circular_linked_list<T>::split_list(circular_linked_list<T>& second_half)
{
Node *tail = find_tail_node();
Node *mid = find_middle_node();
second_half.head = mid->next;
tail->next = second_half.head;
mid->next = head;
}
template <class T>
void circular_linked_list<T>::print_list()
{
Node *tmp = head;
while(tmp->next != head)
{
std::cout << tmp->data << ' ';
tmp = tmp->next;
}
std::cout << tmp->data << '\n';
}
template <class T>
circular_linked_list<T>::~circular_linked_list()
{
Node *tmp = nullptr;
Node *tail = head;
while(tail->next != head)
{
tail = tail->next;
}
tail->next = nullptr;
while(head != nullptr)
{
tmp = head;
head = head->next;
delete tmp;
}
}
int main()
{
circular_linked_list<int> original_list;
original_list.insert_node(2);
original_list.insert_node(3);
original_list.insert_node(4);
original_list.insert_node(1);
original_list.insert_node(0);
std::cout << "The original list is : ";
original_list.print_list();
circular_linked_list<int> second_half;
original_list.split_list(second_half);
//Original list becomes first half
std::cout << "The first half : ";
original_list.print_list();
std::cout << "The second half : ";
second_half.print_list();
}
View this code on Github
Get this post in pdf - Split Circular Linked List
Reference:
Introduction to Algorithms
The Algorithm Design Manual
Data Structures and Algorithms Made Easy
You may also like
Move all Odd numbers after Even numbers in Singly Linked List
Merge two sorted Linked List (in-place)
Doubly Circular Linked List
Reverse the Linked List
Finding Length of Loop in Linked List
Doubly Linked List
Singly Linked List