{"id":26918,"date":"2017-12-26T21:54:20","date_gmt":"2017-12-26T16:24:20","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26918"},"modified":"2017-12-26T21:54:20","modified_gmt":"2017-12-26T16:24:20","slug":"python-algorithm-split-circular-linked-list-two-halves","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-algorithm-split-circular-linked-list-two-halves\/","title":{"rendered":"python algorithm – Split a Circular Linked List into two halves"},"content":{"rendered":"

\"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

Python Programming:<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20split%20circulart%20linked%20list%20into%20two%20halves%0A%20%0A%23%20A%20node%20structure%0Aclass%20Node%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20self.data%20%3D%20data%0A%20%20%20%20%20%20%20%20self.next%20%3D%20None%0A%20%0A%20%0A%23%20Class%20to%20create%20a%20new%20%20Circular%20Linked%20list%0Aclass%20CircularLinkedList%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20empty%20circular%20linked%20list%0A%20%20%20%20def%20__init__(self)%3A%0A%20%20%20%20%20%20%20%20self.head%20%3D%20None%0A%20%0A%20%20%20%20%23%20Function%20to%20insert%20a%20node%20at%20the%20beginning%20of%20a%0A%20%20%20%20%23%20circular%20linked%20list%0A%20%20%20%20def%20push(self%2C%20data)%3A%0A%20%20%20%20%20%20%20%20ptr1%20%3D%20Node(data)%0A%20%20%20%20%20%20%20%20temp%20%3D%20self.head%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20ptr1.next%20%3D%20self.head%0A%20%0A%20%20%20%20%20%20%20%20%23%20If%20linked%20list%20is%20not%20None%20then%20set%20the%20next%20of%0A%20%20%20%20%20%20%20%20%23%20last%20node%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20while(temp.next%20!%3D%20self.head)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%0A%20%20%20%20%20%20%20%20%20%20%20%20temp.next%20%3D%20ptr1%0A%20%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20ptr1.next%20%3D%20ptr1%20%23%20For%20the%20first%20node%0A%20%0A%20%20%20%20%20%20%20%20self.head%20%3D%20ptr1%20%0A%20%0A%20%20%20%20%23%20Function%20to%20print%20nodes%20in%20a%20given%20circular%20linked%20list%0A%20%20%20%20def%20printList(self)%3A%0A%20%20%20%20%20%20%20%20temp%20%3D%20self.head%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20while(True)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print%20%22%25d%22%20%25(temp.data)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20temp%20%3D%20temp.next%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(temp%20%3D%3D%20self.head)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%0A%20%0A%20%20%20%20%23%20Function%20to%20split%20a%20list%20(starting%20with%20head)%20into%20%0A%20%20%20%20%23%20two%20lists.%20head1%20and%20head2%20are%20the%20head%20nodes%20of%20the%0A%20%20%20%20%23%20two%20resultant%20linked%20lists%0A%20%20%20%20def%20splitList(self%2C%20head1%2C%20head2)%3A%0A%20%20%20%20%20%20%20%20slow_ptr%20%3D%20self.head%20%0A%20%20%20%20%20%20%20%20fast_ptr%20%3D%20self.head%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20if%20self.head%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20If%20htere%20are%20odd%20nodes%20in%20the%20circular%20list%20then%0A%20%20%20%20%20%20%20%20%23%20fast_ptr-%3Enext%20becomes%20head%20and%20for%20even%20nodes%0A%20%20%20%20%20%20%20%20%23%20fast_ptr-%3Enext-%3Enext%20becomes%20head%0A%20%20%20%20%20%20%20%20while(fast_ptr.next%20!%3D%20self.head%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20fast_ptr.next.next%20!%3D%20self.head%20)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20fast_ptr%20%3D%20fast_ptr.next.next%0A%20%20%20%20%20%20%20%20%20%20%20%20slow_ptr%20%3D%20slow_ptr.next%0A%20%0A%20%20%20%20%20%20%20%20%23%20If%20there%20are%20event%20elements%20in%20list%20then%0A%20%20%20%20%20%20%20%20%23%20move%20fast_ptr%0A%20%20%20%20%20%20%20%20if%20fast_ptr.next.next%20%3D%3D%20self.head%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20fast_ptr%20%3D%20fast_ptr.next%0A%20%0A%20%20%20%20%20%20%20%20%23%20Set%20the%20head%20pointer%20of%20first%20half%0A%20%20%20%20%20%20%20%20head1.head%20%3D%20self.head%0A%20%0A%20%20%20%20%20%20%20%20%23%20Set%20the%20head%20pointer%20of%20second%20half%0A%20%20%20%20%20%20%20%20if%20self.head.next%20!%3D%20self.head%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20head2.head%20%3D%20slow_ptr.next%0A%20%0A%20%20%20%20%20%20%20%20%23%20Make%20second%20half%20circular%0A%20%20%20%20%20%20%20%20fast_ptr.next%20%3D%20slow_ptr.next%0A%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%23%20Make%20first%20half%20circular%0A%20%20%20%20%20%20%20%20slow_ptr.next%20%3D%20self.head%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20above%20functions%0A%20%0A%23%20Initialize%20lists%20as%20empty%0Ahead%20%3D%20CircularLinkedList()%20%0Ahead1%20%3D%20CircularLinkedList()%0Ahead2%20%3D%20CircularLinkedList()%0A%20%0Ahead.push(12)%0Ahead.push(56)%0Ahead.push(2)%0Ahead.push(11)%0A%20%0Aprint%20%22Original%20Circular%20Linked%20List%22%0Ahead.printList()%0A%20%0A%23%20Split%20the%20list%20%0Ahead.splitList(head1%20%2C%20head2)%0A%20%0Aprint%20%22%5CnFirst%20Circular%20Linked%20List%22%0Ahead1.printList()%0A%20%0Aprint%20%22%5CnSecond%20Circular%20Linked%20List%22%0Ahead2.printList()\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n

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

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":"
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,4148],"tags":[80242,80246,80247,80243,80245,80244,80249,80248],"class_list":["post-26918","post","type-post","status-publish","format-standard","hentry","category-circular-linked-list","category-linked-list","category-python","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\/26918","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=26918"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26918\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26918"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26918"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26918"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}