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

<\/div> 
\/\/ Java program to delete a node from doubly linked list class LinkedList {     static Node head, head1, head2;     static class Node {         int data;        Node next, prev;         Node(int d) {            data = d;            next = prev = null;        }    }     \/* Function to split a list (starting with head) into two lists.     head1_ref and head2_ref are references to head nodes of      the two resultant linked lists *\/    void splitList() {        Node slow_ptr = head;        Node fast_ptr = head;         if (head == null) {            return;        }         \/* If there are odd nodes in the circular list then         fast_ptr->next becomes head and for even nodes          fast_ptr->next->next becomes head *\/        while (fast_ptr.next != head                && fast_ptr.next.next != head) {            fast_ptr = fast_ptr.next.next;            slow_ptr = slow_ptr.next;        }         \/* If there are even elements in list then move fast_ptr *\/        if (fast_ptr.next.next == head) {            fast_ptr = fast_ptr.next;        }         \/* Set the head pointer of first half *\/        head1 = head;         \/* Set the head pointer of second half *\/        if (head.next != head) {            head2 = slow_ptr.next;        }        \/* Make second half circular *\/        fast_ptr.next = slow_ptr.next;         \/* Make first half circular *\/        slow_ptr.next = head;    }     \/* Function to print nodes in a given singly linked list *\/    void printList(Node node) {        Node temp = node;        if (node != null) {            do {                System.out.print(temp.data + " ");                temp = temp.next;            } while (temp != node);        }    }     public static void main(String[] args) {        LinkedList list = new LinkedList();         \/\/Created linked list will be 12->56->2->11        list.head = new Node(12);        list.head.next = new Node(56);        list.head.next.next = new Node(2);        list.head.next.next.next = new Node(11);        list.head.next.next.next.next = list.head;         System.out.println("Original Circular Linked list ");        list.printList(head);         \/\/ Split the list        list.splitList();        System.out.println("");        System.out.println("First Circular List ");        list.printList(head1);        System.out.println("");        System.out.println("Second Circular List ");        list.printList(head2);             }}<\/code><\/pre> <\/div>\n[ad type=”banner”]\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}]}}