{"id":26888,"date":"2017-12-26T20:42:58","date_gmt":"2017-12-26T15:12:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26888"},"modified":"2017-12-26T20:42:59","modified_gmt":"2017-12-26T15:12:59","slug":"c-algorithm-split-circular-linked-list-two-halves","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-split-circular-linked-list-two-halves\/","title":{"rendered":"C++ algorithm &#8211; Split a Circular Linked List into two halves"},"content":{"rendered":"<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-26892\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_orig-1.png\" alt=\"Split a Circular Linked List into two halves\" width=\"722\" height=\"180\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_orig-1.png 722w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_orig-1-300x75.png 300w\" sizes=\"(max-width: 722px) 100vw, 722px\" \/><\/p>\n<h3 id=\"original-linked-list\" style=\"text-align: center;\">Original Linked List<\/h3>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-26893\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_split1.png\" alt=\"Split a Circular Linked List into two halves\" width=\"429\" height=\"174\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_split1.png 429w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_split1-300x122.png 300w\" sizes=\"(max-width: 429px) 100vw, 429px\" \/><\/p>\n<h3 id=\"result-linked-list-1\" style=\"text-align: center;\">Result Linked List 1<\/h3>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-26894\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_split2.png\" alt=\"Split a Circular Linked List into two halves\" width=\"432\" height=\"174\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_split2.png 432w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/cll_split2-300x121.png 300w\" sizes=\"(max-width: 432px) 100vw, 432px\" \/><\/p>\n<h3 id=\"result-linked-list-2\" style=\"text-align: center;\">Result Linked List 2<\/h3>\n<p>C Programming<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20Program%20to%20split%20a%20circular%20linked%20list%20into%20two%20halves%20*%2F%0A%23include%3Cstdio.h%3E%20%0A%23include%3Cstdlib.h%3E%20%0A%20%0A%2F*%20structure%20for%20a%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20int%20data%3B%0A%20%20struct%20node%20*next%3B%0A%7D%3B%20%0A%20%0A%2F*%20Function%20to%20split%20a%20list%20(starting%20with%20head)%20into%20two%20lists.%0A%20%20%20head1_ref%20and%20head2_ref%20are%20references%20to%20head%20nodes%20of%20%0A%20%20%20%20the%20two%20resultant%20linked%20lists%20*%2F%0Avoid%20splitList(struct%20node%20*head%2C%20struct%20node%20**head1_ref%2C%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20struct%20node%20**head2_ref)%0A%7B%0A%20%20struct%20node%20*slow_ptr%20%3D%20head%3B%0A%20%20struct%20node%20*fast_ptr%20%3D%20head%3B%20%0A%20%0A%20%20if(head%20%3D%3D%20NULL)%0A%20%20%20%20return%3B%0A%20%20%0A%20%20%2F*%20If%20there%20are%20odd%20nodes%20in%20the%20circular%20list%20then%0A%20%20%20%20%20fast_ptr-%3Enext%20becomes%20head%20and%20for%20even%20nodes%20%0A%20%20%20%20%20fast_ptr-%3Enext-%3Enext%20becomes%20head%20*%2F%0A%20%20while(fast_ptr-%3Enext%20!%3D%20head%20%26%26%0A%20%20%20%20%20%20%20%20%20fast_ptr-%3Enext-%3Enext%20!%3D%20head)%20%0A%20%20%7B%0A%20%20%20%20%20fast_ptr%20%3D%20fast_ptr-%3Enext-%3Enext%3B%0A%20%20%20%20%20slow_ptr%20%3D%20slow_ptr-%3Enext%3B%0A%20%20%7D%20%20%0A%20%0A%20%2F*%20If%20there%20are%20even%20elements%20in%20list%20then%20move%20fast_ptr%20*%2F%0A%20%20if(fast_ptr-%3Enext-%3Enext%20%3D%3D%20head)%0A%20%20%20%20fast_ptr%20%3D%20fast_ptr-%3Enext%3B%20%20%20%20%20%20%0A%20%20%20%0A%20%20%2F*%20Set%20the%20head%20pointer%20of%20first%20half%20*%2F%0A%20%20*head1_ref%20%3D%20head%3B%20%20%20%20%0A%20%20%20%20%20%20%0A%20%20%2F*%20Set%20the%20head%20pointer%20of%20second%20half%20*%2F%0A%20%20if(head-%3Enext%20!%3D%20head)%0A%20%20%20%20*head2_ref%20%3D%20slow_ptr-%3Enext%3B%0A%20%20%20%0A%20%20%2F*%20Make%20second%20half%20circular%20*%2F%20%20%0A%20%20fast_ptr-%3Enext%20%3D%20slow_ptr-%3Enext%3B%0A%20%20%20%0A%20%20%2F*%20Make%20first%20half%20circular%20*%2F%20%20%0A%20%20slow_ptr-%3Enext%20%3D%20head%3B%20%20%20%20%20%20%20%0A%7D%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20begining%20of%20a%20Circular%20%0A%20%20%20linked%20lsit%20*%2F%0Avoid%20push(struct%20node%20**head_ref%2C%20int%20data)%0A%7B%0A%20%20struct%20node%20*ptr1%20%3D%20(struct%20node%20*)malloc(sizeof(struct%20node))%3B%0A%20%20struct%20node%20*temp%20%3D%20*head_ref%3B%20%0A%20%20ptr1-%3Edata%20%3D%20data%3B%20%20%0A%20%20ptr1-%3Enext%20%3D%20*head_ref%3B%20%0A%20%20%20%0A%20%20%2F*%20If%20linked%20list%20is%20not%20NULL%20then%20set%20the%20next%20of%20%0A%20%20%20%20last%20node%20*%2F%0A%20%20if(*head_ref%20!%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20while(temp-%3Enext%20!%3D%20*head_ref)%0A%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%20%20%20%20%20%20%20%20%0A%20%20%20%20temp-%3Enext%20%3D%20ptr1%3B%20%0A%20%20%7D%0A%20%20else%0A%20%20%20%20%20ptr1-%3Enext%20%3D%20ptr1%3B%20%2F*For%20the%20first%20node%20*%2F%0A%20%0A%20%20*head_ref%20%3D%20ptr1%3B%20%20%20%20%20%0A%7D%20%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20Circular%20linked%20list%20*%2F%0Avoid%20printList(struct%20node%20*head)%0A%7B%0A%20%20struct%20node%20*temp%20%3D%20head%3B%20%0A%20%20if(head%20!%3D%20NULL)%0A%20%20%7B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%20%20%20%20do%20%7B%0A%20%20%20%20%20%20printf(%22%25d%20%22%2C%20temp-%3Edata)%3B%0A%20%20%20%20%20%20temp%20%3D%20temp-%3Enext%3B%0A%20%20%20%20%7D%20while(temp%20!%3D%20head)%3B%0A%20%20%7D%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0Aint%20main()%0A%7B%0A%20%20int%20list_size%2C%20i%3B%20%0A%20%20%20%0A%20%20%2F*%20Initialize%20lists%20as%20empty%20*%2F%0A%20%20struct%20node%20*head%20%3D%20NULL%3B%0A%20%20struct%20node%20*head1%20%3D%20NULL%3B%0A%20%20struct%20node%20*head2%20%3D%20NULL%3B%20%20%0A%20%0A%20%20%2F*%20Created%20linked%20list%20will%20be%2012-%3E56-%3E2-%3E11%20*%2F%0A%20%20push(%26head%2C%2012)%3B%20%0A%20%20push(%26head%2C%2056)%3B%20%20%20%0A%20%20push(%26head%2C%202)%3B%20%20%20%0A%20%20push(%26head%2C%2011)%3B%20%20%20%0A%20%0A%20%20printf(%22Original%20Circular%20Linked%20List%22)%3B%0A%20%20printList(head)%3B%20%20%20%20%20%20%0A%20%20%0A%20%20%2F*%20Split%20the%20list%20*%2F%0A%20%20splitList(head%2C%20%26head1%2C%20%26head2)%3B%0A%20%20%0A%20%20printf(%22%5CnFirst%20Circular%20Linked%20List%22)%3B%0A%20%20printList(head1)%3B%20%20%0A%20%0A%20%20printf(%22%5CnSecond%20Circular%20Linked%20List%22)%3B%0A%20%20printList(head2)%3B%20%20%0A%20%20%20%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D%20\u2033 message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n<p><strong>Output:<\/strong><\/p>\n<pre>Original Circular Linked List\r\n11 2 56 12 \r\nFirst Circular Linked List\r\n11 2 \r\nSecond Circular Linked List\r\n56 12<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Split a Circular Linked List into two halves- Circular Linked List Original Linked List , Result Linked List 1 , Result Linked List 2.<\/p>\n","protected":false},"author":1,"featured_media":0,"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-26888","post","type-post","status-publish","format-standard","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\/26888","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=26888"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26888\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}