# Python program to split circulart linked list into two halves
 
# A node structure
class Node:
     
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
# Class to create a new  Circular Linked list
class CircularLinkedList:
     
    # Constructor to create a empty circular linked list
    def __init__(self):
        self.head = None
 
    # Function to insert a node at the beginning of a
    # circular linked list
    def push(self, data):
        ptr1 = Node(data)
        temp = self.head
         
        ptr1.next = self.head
 
        # If linked list is not None then set the next of
        # last node
        if self.head is not None:
            while(temp.next != self.head):
                temp = temp.next
            temp.next = ptr1
 
        else:
            ptr1.next = ptr1 # For the first node
 
        self.head = ptr1 
 
    # Function to print nodes in a given circular linked list
    def printList(self):
        temp = self.head
        if self.head is not None:
            while(True):
                print "%d" %(temp.data),
                temp = temp.next
                if (temp == self.head):
                    break
 
 
    # Function to split a list (starting with head) into 
    # two lists. head1 and head2 are the head nodes of the
    # two resultant linked lists
    def splitList(self, head1, head2):
        slow_ptr = self.head 
        fast_ptr = self.head
     
        if self.head is None:
            return
         
        # If htere 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 != self.head and
            fast_ptr.next.next != self.head ):
            fast_ptr = fast_ptr.next.next
            slow_ptr = slow_ptr.next
 
        # If there are event elements in list then
        # move fast_ptr
        if fast_ptr.next.next == self.head:
            fast_ptr = fast_ptr.next
 
        # Set the head pointer of first half
        head1.head = self.head
 
        # Set the head pointer of second half
        if self.head.next != self.head:
            head2.head = slow_ptr.next
 
        # Make second half circular
        fast_ptr.next = slow_ptr.next
     
        # Make first half circular
        slow_ptr.next = self.head
 
 
# Driver program to test above functions
 
# Initialize lists as empty
head = CircularLinkedList() 
head1 = CircularLinkedList()
head2 = CircularLinkedList()
 
head.push(12)
head.push(56)
head.push(2)
head.push(11)
 
print "Original Circular Linked List"
head.printList()
 
# Split the list 
head.splitList(head1 , head2)
 
print "\nFirst Circular Linked List"
head1.printList()
 
print "\nSecond Circular Linked List"
head2.printList()