Chapter 3, Problem 23C

Explanation of Solution

Algorithm:

1. 1. The mid and last of the circular linked list is stored using tortoise and hare algorithm.
2. 2. Make the second half circular.
3. 3. Make the first half circular.
4. 4. Set the head (or start) pointer of the two linked lists.

Program code:

//include the required header files

#include<stdio.h> 

#include<stdlib.h> 

Using namespace std;

// structure for a node

struct Node

{

int data;

struct Node *next;

};

/* Function to split a list (starting with head) into two lists.

head1_ref and head2_ref are references to head nodes of 

the two resultant linked lists */

void splitList(struct Node *head, struct Node **head1_ref,

struct Node **head2_ref)

{

struct Node *slow_ptr = head;

struct Node *fast_ptr = head; 

if(head == NULL)

    return;

/* If there are odd nodes in the circular list then

fast_ptr->next becomes head and for even nodes 

fast_ptr->next->next becomes head */

while(fast_ptr->next != head &&

fast_ptr->next->next != head) 

{

fast_ptr = fast_ptr->next->next;

slow_ptr = slow_ptr->next;

}

// If there are even elements in list then move fast_ptr

if(fast_ptr->next->next == head)

    fast_ptr = fast_ptr->next;

// Set the head pointer of first half

*head1_ref = head;

// Set the head pointer of second half

if(head->next != head)

    *head2_ref = slow_ptr->next;

// Make second half circular   

fast_ptr->next = slow_ptr->next;

//Make first half circular

slow_ptr->next = head;

}

// Function to insert a node at the beginning of a Circular  linked list

void push(struct Node **head_ref, int data)

{

struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));

struct Node *temp = *head_ref; 

ptr1->data = data;  

ptr1->next = *head_ref; 

// If linked list is not NULL then set the next of  last node

if(*head_ref != NULL)

{

while(temp->next != *head_ref)

    temp = temp->next;

temp->next = ptr1; 

}

else

  /*For the first node */

  ptr1->next = ptr1;

*head_ref = ptr1;     

}

// Function to print nodes in a given Circular linked list

void printList(struct Node *head)

{