Linked List: Split a circular linked list into two halves

Problem Statement:

Split a circular linked list into two halves

If there are odd number of nodes, then first node should have one more than second list.

Example:

1 -> 2 -> 3
^         ^
| - - - - |

Output:

1 -> 2

3

Solution Explanation:

Find the middle node and the last node using fast and slow pointer.

If the list has odd number of nodes, the fast pointer will reach the last node.

If the lost has even number, it will stop before the last node.

Once we get the middle node, first half starts from the head, and second will start from the node after the middle node.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

class Node 
{ 
    public:
    int data; 
    Node *next; 
    Node (int new_value)
    {
        data = new_value;
        next = NULL;
    }
}; 


pair<Node*, Node*> solution(Node *head) 
{ 

    Node *slow = head; 
    Node *fast = head; 
    
    if(head == NULL) 
        return {NULL, NULL}; 
        

    while(fast->next != head && 
          fast->next->next != head) 
          { 

        fast = fast->next->next; 
        slow = slow->next; 
    } 
    
    if(fast->next->next == head) 
        fast = fast->next; 
        
    Node* head1 = head; 
        
    Node* head2 = slow->next; 
        
    fast->next = slow->next; 
        
    slow->next = head; 
    
    return {head1, head2};
} 

void print_list(Node *head) 
{ 
    Node *curr = head; 
    if(head != nullptr) 
    { 
        do { 
        cout << curr->data << " "; 
        curr = curr->next; 
        } while(curr != head); 
      	cout << endl; 
    } 
} 

int main() 
{ 
    
    Node *head = new Node(1); 
    Node *head1 = nullptr; 
    Node *head2 = nullptr; 

    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = head;
    
    pair<Node*, Node*> result = solution(head); 
    
    head1 = result.first;
    head2 = result.second;
    
    print_list(head1); 
    print_list(head2);
    
    return 0; 
} 

Output

1 2 
3 4