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

Split Linked List

Split 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