{"id":26914,"date":"2017-12-26T21:18:58","date_gmt":"2017-12-26T15:48:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26914"},"modified":"2018-10-27T18:12:32","modified_gmt":"2018-10-27T12:42:32","slug":"java-algorithm-split-circular-linked-list-two-halves","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-algorithm-split-circular-linked-list-two-halves\/","title":{"rendered":"Split a Circular Linked List into two halves"},"content":{"rendered":"

Circular Linked List:<\/span><\/h2>\n

Circular Linked List is a list in which all nodes are connected to form circle<\/strong>. Here, the last node points to the first node<\/strong> in the list. Implemented by singly linked list or doubly linked list.<\/p>\n

<\/h3>\n

\"Split<\/h3>\n

Original Linked List<\/h3>\n

\"Split\"Split<\/p>\n

Result Linked List 1<\/h3>\n

\"Split<\/p>\n

Result Linked List 2<\/h3>\n

Split a Circular Linked List into two halves:\u00a0<\/strong><\/span><\/h4>\n

Example:<\/strong> Explained through java program<\/a>.<\/p>\n

Java programming:<\/strong><\/span><\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%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\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n

Output:<\/strong><\/span><\/p>\n

Original Circular Linked List\r\n12 56 2 11\r\nFirst Circular Linked List\r\n12 56\r\nSecond Circular Linked List\r\n2 11<\/pre>\n","protected":false},"excerpt":{"rendered":"
Split a Circular Linked List into two halves – Circular Linked List is a list in which all nodes are connected to form circle.<\/p>\n","protected":false},"author":1,"featured_media":31596,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[79477,79476],"tags":[80242,80246,80247,80243,80245,80244,80249,80248],"class_list":["post-26914","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-circular-linked-list","category-linked-list","tag-check-if-linked-list-is-palindrome-java","tag-doubly-linked-list-palindrome","tag-doubly-linked-list-palindrome-java","tag-java-program-palindrome-with-linked-lists","tag-palindrome-checking-using-doubly-linked-list-in-c","tag-palindrome-linked-list-python","tag-palindrome-list-interviewbit","tag-singly-linked-list-palindrome-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26914","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26914"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26914\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31596"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26914"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26914"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26914"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}