{"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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">\/* Program to split a circular linked list into two halves *\/<br\/>#include&lt;stdio.h&gt; <br\/>#include&lt;stdlib.h&gt; <br\/> <br\/>\/* structure for a node *\/<br\/>struct node<br\/>{<br\/>  int data;<br\/>  struct node *next;<br\/>}; <br\/> <br\/>\/* Function to split a list (starting with head) into two lists.<br\/>   head1_ref and head2_ref are references to head nodes of <br\/>    the two resultant linked lists *\/<br\/>void splitList(struct node *head, struct node **head1_ref, <br\/>                                            struct node **head2_ref)<br\/>{<br\/>  struct node *slow_ptr = head;<br\/>  struct node *fast_ptr = head; <br\/> <br\/>  if(head == NULL)<br\/>    return;<br\/>  <br\/>  \/* If there are odd nodes in the circular list then<br\/>     fast_ptr-&gt;next becomes head and for even nodes <br\/>     fast_ptr-&gt;next-&gt;next becomes head *\/<br\/>  while(fast_ptr-&gt;next != head &amp;&amp;<br\/>         fast_ptr-&gt;next-&gt;next != head) <br\/>  {<br\/>     fast_ptr = fast_ptr-&gt;next-&gt;next;<br\/>     slow_ptr = slow_ptr-&gt;next;<br\/>  }  <br\/> <br\/> \/* If there are even elements in list then move fast_ptr *\/<br\/>  if(fast_ptr-&gt;next-&gt;next == head)<br\/>    fast_ptr = fast_ptr-&gt;next;      <br\/>   <br\/>  \/* Set the head pointer of first half *\/<br\/>  *head1_ref = head;    <br\/>      <br\/>  \/* Set the head pointer of second half *\/<br\/>  if(head-&gt;next != head)<br\/>    *head2_ref = slow_ptr-&gt;next;<br\/>   <br\/>  \/* Make second half circular *\/  <br\/>  fast_ptr-&gt;next = slow_ptr-&gt;next;<br\/>   <br\/>  \/* Make first half circular *\/  <br\/>  slow_ptr-&gt;next = head;       <br\/>}<br\/> <br\/>\/* UTILITY FUNCTIONS *\/<br\/>\/* Function to insert a node at the begining of a Circular <br\/>   linked lsit *\/<br\/>void push(struct node **head_ref, int data)<br\/>{<br\/>  struct node *ptr1 = (struct node *)malloc(sizeof(struct node));<br\/>  struct node *temp = *head_ref; <br\/>  ptr1-&gt;data = data;  <br\/>  ptr1-&gt;next = *head_ref; <br\/>   <br\/>  \/* If linked list is not NULL then set the next of <br\/>    last node *\/<br\/>  if(*head_ref != NULL)<br\/>  {<br\/>    while(temp-&gt;next != *head_ref)<br\/>      temp = temp-&gt;next;        <br\/>    temp-&gt;next = ptr1; <br\/>  }<br\/>  else<br\/>     ptr1-&gt;next = ptr1; \/*For the first node *\/<br\/> <br\/>  *head_ref = ptr1;     <br\/>} <br\/> <br\/>\/* Function to print nodes in a given Circular linked list *\/<br\/>void printList(struct node *head)<br\/>{<br\/>  struct node *temp = head; <br\/>  if(head != NULL)<br\/>  {<br\/>    printf(&quot;\\n&quot;);<br\/>    do {<br\/>      printf(&quot;%d &quot;, temp-&gt;data);<br\/>      temp = temp-&gt;next;<br\/>    } while(temp != head);<br\/>  }<br\/>}<br\/> <br\/>\/* Driver program to test above functions *\/<br\/>int main()<br\/>{<br\/>  int list_size, i; <br\/>   <br\/>  \/* Initialize lists as empty *\/<br\/>  struct node *head = NULL;<br\/>  struct node *head1 = NULL;<br\/>  struct node *head2 = NULL;  <br\/> <br\/>  \/* Created linked list will be 12-&gt;56-&gt;2-&gt;11 *\/<br\/>  push(&amp;head, 12); <br\/>  push(&amp;head, 56);   <br\/>  push(&amp;head, 2);   <br\/>  push(&amp;head, 11);   <br\/> <br\/>  printf(&quot;Original Circular Linked List&quot;);<br\/>  printList(head);      <br\/>  <br\/>  \/* Split the list *\/<br\/>  splitList(head, &amp;head1, &amp;head2);<br\/>  <br\/>  printf(&quot;\\nFirst Circular Linked List&quot;);<br\/>  printList(head1);  <br\/> <br\/>  printf(&quot;\\nSecond Circular Linked List&quot;);<br\/>  printList(head2);  <br\/>   <br\/>  getchar();<br\/>  return 0;<br\/>} <\/code><\/pre> <\/div>\n[ad type=&#8221;banner&#8221;]\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}]}}