Circular Linked List:
Circular Linked List is a list in which all nodes are connected to form circle. Here, the last node points to the first node in the list. Implemented by singly linked list or doubly linked list.
Original Linked List
Result Linked List 1
Result Linked List 2
Split a Circular Linked List into two halves:
Example: Explained through java program.
Java programming:
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20delete%20a%20node%20from%20doubly%20linked%20list%0A%20%0Aclass%20LinkedList%20%7B%0A%20%0A%20%20%20%20static%20Node%20head%2C%20head1%2C%20head2%3B%0A%20%0A%20%20%20%20static%20class%20Node%20%7B%0A%20%0A%20%20%20%20%20%20%20%20int%20data%3B%0A%20%20%20%20%20%20%20%20Node%20next%2C%20prev%3B%0A%20%0A%20%20%20%20%20%20%20%20Node(int%20d)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20data%20%3D%20d%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20next%20%3D%20prev%20%3D%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Function%20to%20split%20a%20list%20(starting%20with%20head)%20into%20two%20lists.%0A%20%20%20%20%20head1_ref%20and%20head2_ref%20are%20references%20to%20head%20nodes%20of%20%0A%20%20%20%20%20the%20two%20resultant%20linked%20lists%20*%2F%0A%20%20%20%20void%20splitList()%20%7B%0A%20%20%20%20%20%20%20%20Node%20slow_ptr%20%3D%20head%3B%0A%20%20%20%20%20%20%20%20Node%20fast_ptr%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(head%20%3D%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20there%20are%20odd%20nodes%20in%20the%20circular%20list%20then%0A%20%20%20%20%20%20%20%20%20fast_ptr-%3Enext%20becomes%20head%20and%20for%20even%20nodes%20%0A%20%20%20%20%20%20%20%20%20fast_ptr-%3Enext-%3Enext%20becomes%20head%20*%2F%0A%20%20%20%20%20%20%20%20while%20(fast_ptr.next%20!%3D%20head%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%26%26%20fast_ptr.next.next%20!%3D%20head)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20fast_ptr%20%3D%20fast_ptr.next.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20slow_ptr%20%3D%20slow_ptr.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20If%20there%20are%20even%20elements%20in%20list%20then%20move%20fast_ptr%20*%2F%0A%20%20%20%20%20%20%20%20if%20(fast_ptr.next.next%20%3D%3D%20head)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20fast_ptr%20%3D%20fast_ptr.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Set%20the%20head%20pointer%20of%20first%20half%20*%2F%0A%20%20%20%20%20%20%20%20head1%20%3D%20head%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Set%20the%20head%20pointer%20of%20second%20half%20*%2F%0A%20%20%20%20%20%20%20%20if%20(head.next%20!%3D%20head)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20head2%20%3D%20slow_ptr.next%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%2F*%20Make%20second%20half%20circular%20*%2F%0A%20%20%20%20%20%20%20%20fast_ptr.next%20%3D%20slow_ptr.next%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F*%20Make%20first%20half%20circular%20*%2F%0A%20%20%20%20%20%20%20%20slow_ptr.next%20%3D%20head%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20singly%20linked%20list%20*%2F%0A%20%20%20%20void%20printList(Node%20node)%20%7B%0A%20%20%20%20%20%20%20%20Node%20temp%20%3D%20node%3B%0A%20%20%20%20%20%20%20%20if%20(node%20!%3D%20null)%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20do%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(temp.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%20while%20(temp%20!%3D%20node)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20public%20static%20void%20main(String%5B%5D%20args)%20%7B%0A%20%20%20%20%20%20%20%20LinkedList%20list%20%3D%20new%20LinkedList()%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2FCreated%20linked%20list%20will%20be%2012-%3E56-%3E2-%3E11%0A%20%20%20%20%20%20%20%20list.head%20%3D%20new%20Node(12)%3B%0A%20%20%20%20%20%20%20%20list.head.next%20%3D%20new%20Node(56)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next%20%3D%20new%20Node(2)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next%20%3D%20new%20Node(11)%3B%0A%20%20%20%20%20%20%20%20list.head.next.next.next.next%20%3D%20list.head%3B%0A%20%0A%20%20%20%20%20%20%20%20System.out.println(%22Original%20Circular%20Linked%20list%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Split%20the%20list%0A%20%20%20%20%20%20%20%20list.splitList()%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22First%20Circular%20List%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head1)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Second%20Circular%20List%20%22)%3B%0A%20%20%20%20%20%20%20%20list.printList(head2)%3B%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%7D%0A%7D” message=”” highlight=”” provider=”manual”/] [ad type=”banner”]Output:
Original Circular Linked List 12 56 2 11 First Circular Linked List 12 56 Second Circular Linked List 2 11