Chapter 3, Problem 30C

Explanation of Solution

Algorithm to split the circularly linked list:

The algorithm to split the two half of circularly linked list “L” is given below:

Algorithm:

Input: circularly linked list “L” contains even number of nodes.

Output: Split the “L” into two half of circularly linked list “L” and “M”.

split(L):

  //Create circularly linked list "M"

  CircularlyLinkedList M = new CircularlyLinkedList()   

/*Create node for temporary use and assign tail of list "L" into it. */

  Node temp = L.tail;

//Loop executes until the half of size of list "L"

  for i less than half of "L" size, then

/*Get next node of tail and assign it into "temp" node. */

  temp = temp.getNext();

/*Get the next node of "temp" node and assign it into tail of "M" list. */

  M.tail = temp.getNext();

/*Set the next node of "temp" node as the tail of list "L". */

  temp.setNext(L.tail);

//Loop executes until the half of size of list "L"

  for i less than half of "L" size, then

/*Get next node of tail and assign it into "temp" node...