CareerCup

traverse the circular list with 2 points "first and second"
increment first by 2 times and second once till you read the head pointer again.
after the first travelsal, first will be pointing to head of list and second will be at the mid point.
we will be left with setting the next pointers to null and returning 2 pointer (first and second)

//first points to start if the list
void circular_to_list(struct node *first, struct node *second)
{
    struct node *head, struct node *temp;
    head = first;
    second = head;
    first = head;
    do
    {
        first = first->next;
        if(first == temp)
            break;
        first = first->temp;
        second = second->next;
    }while(first != temp);

    //first is pointing to head of list
    //second is point to mid of the list
    temp = first;
    first = first->next;
    temp->next = NULL;
    temp = second;
    second = second->next;
    second->next = NULL;
}

Take 3 pointer from start ..
Increase 1st by 4 times,
Increase 2nd by 2 times,
Increase 3rd by 1 times,

When 1st and 2nd will be meeting for first time, 3rd pointer will on mid

We can start with head and assign first node to list1 and next node to list2 and so on... till all the node && node->next are not equal.
But,what if no. of nodes in list has odd value?

Take two pointer of any node, let X. Increment one pointer by one and other by two. when 2nd pointer will again reach to the X then first one will be in the middle of list.Then we will have two list of equal length. First ones starting address will be X and other ones will be 1st pointer.And along with this we need to make lastNode->next=null for both the list.

This is same as finding middle element in a link-list by single traversal . Take t1o pointer one runs single increment one 2*single increment. When reached to the middle point split them. Stop condition will not be NULL here but the head pointer.

Use fast & slow pointer concept ....easy one from Adobe...

Use fast & slow pointer concept ....easy one from Adobe...

Solution given will work for a circular single linked list that has even number of nodes, what if there are odd number of nodes as ptripa pointed out ?

package com.career.ds.linkedlist;

public class SplitCircularList {

    public static void main(String args[]) {
        CreateCircularList ll = new CreateCircularList();
        Node head = ll.createList(7, 1);
        ll.displayCircularList(head);
        Node secondHead =  ll.splitList(head);
        ll.displayCircularList(head);
        ll.displayCircularList(secondHead);
    }
}

class CreateCircularList {

    public Node createList(int length, int data) {
        Node head = new Node((data++));
        Node pointer = head;
        for (int i = 1; i < length; i++) {
            Node temp = new Node((data++));
            pointer.setNext(temp);
            pointer = temp;
        }
        pointer.setNext(head);
        return head;
    }

    public void displayCircularList(Node head) {
        Node temp = head;
        while (temp.getNext() != head) {
            System.out.print(temp.getData() + "->");
            temp = temp.getNext();
        }
        System.out.println(temp.getData() + "->");
    }
    
    public Node splitList(Node head) {
        Node tortoisePointer = head;
        Node harePointer = head.getNext();
        
        while(harePointer != head && harePointer.getNext() != head) {
            harePointer = harePointer.getNext().getNext();
            tortoisePointer = tortoisePointer.getNext();
        }
        Node secondHead = tortoisePointer.getNext();
        tortoisePointer.setNext(head);
        Node temp = secondHead;
        while(temp.getNext() != head) {
            temp = temp.getNext();
        }
        temp.setNext(secondHead);
        return secondHead;
    }
}

Odd
===

1->2->3->4->5->6->7->
1->2->3->4->
5->6->7->

Even
====

1->2->3->4->5->6->7->8->
1->2->3->4->
5->6->7->8->

private void splitNode(LLNode head){
		
		
		LLNode temp = head;
		int count = 0;
		
		//count total nodes
		while(temp.next!=head){
			
			count++;
			temp = temp.next;
		}
		
		temp = head;
		
		int i=0;
		while(i!=count/2){
			
			temp=temp.next;
			i++;
			
		}
		//go to middle and ground the node also mark the next node as 
		//head of second LL
		LLNode newHead = temp.next;
		
		temp.next = null;
		
		temp = newHead;
		while(temp.next!=head){
			temp=temp.next;
		}
		//ground the last node of second list
		temp.next=null;
		
		
		
		
	}

Take 3 pointer from start ..
Increase 1st by 4 times,
Increase 2nd by 2 times,
Increase 3rd by 1 times,

When 1st and 2nd will be meeting for first time, 3rd pointer will on mid

Given a circular linked list with head pointer head.

Here is another approach....

1. Turn circular list into singly linked list by inserting a null pointer.

temp = head->next;
head->next = null;
head = temp;

Now we have a singly linked list with new head pointer.

2. Now use two pointers, first moves one step at a time while second moves two step at a time. When second reaches the end, first is at middle. Now we can break the list at the middle.

first = head;
second = head;
while(second!= NULL && second->next != NULL)
{
first = first->next;
second = second->next->next;
}

BreakCircular( Linked *head)
{
Linked * ptr1 , *ptr2, head1;
ptr1 = ptr2 = Head;
int move =0;

while( Ptr2->next != Head)
{
ptr1 = ptr1->next;
i++;
if( i%2 == 0)
{
ptr1 = ptr1->next;
}
}
head1 = ptr1->next;
ptr1->next = NULL;
ptr2->next = NULL;
}
}

start off in clockwise and anticlockwise from single node and travese till they both meet.