Dividir una lista enlazada circular en tres mitades de casi el mismo tamaño

Dividir la lista enlazada circular dada en tres mitades sin calcular su longitud de modo que la diferencia entre una lista enlazada con un número máximo de Nodes y una lista enlazada con un número mínimo de Nodes sea mínima.

Ejemplos :

Entrada : Lista enlazada circular: 1->3->5->7->9
Salida : 1 3
              5 7
               9

Entrada : Lista enlazada circular: 2->4->8
Salida : 2 
              4
             8

Enfoque : El enfoque para resolver este problema es usar el algoritmo de Turtle y liebre.

• Mueva los punteros lento, promedio y rápido 1, 2 y 3
• Cuando el indicador rápido llegó a NULL, el indicador promedio llegó al final de las segundas mitades y el indicador lento llegó al final de las primeras mitades.
• Haz la Tercera mitad circular.
• Haz la segunda mitad circular.
• Haz la primera mitad circular.
• Establecer punteros de cabeza de las dos listas enlazadas

A continuación se muestra la implementación del enfoque anterior:

// Program to split a circular linked list
// into three halves
#include <bits/stdc++.h>
using namespace std;
 
/* structure for a node */
class Node {
public:
    int data;
    Node* next;
};
 
// Function to split a list
// (starting with head) into three lists.
// head1_ref, head2_ref & head3_ref are
// references to head nodes of the
// three resultant linked lists
void splitList(Node* head, Node** head1_ref,
               Node** head2_ref,
               Node** head3_ref)
{
    Node* slow_ptr = head;
    Node* avg_ptr = head->next;
    Node* fast_ptr = head->next->next;
 
    if (head == NULL
        || head->next == NULL
        || head->next->next == NULL)
        return;
 
    while (fast_ptr->next != head
           && fast_ptr->next->next != head) {
 
        if (fast_ptr->next->next->next
            != head)
            fast_ptr
                = fast_ptr->next->next->next;
        else {
            fast_ptr = fast_ptr->next->next;
        }
        avg_ptr = avg_ptr->next->next;
        slow_ptr = slow_ptr->next;
    }
 
    while (fast_ptr->next != head)
        fast_ptr = fast_ptr->next;
 
    // Make third half circular
    *head3_ref = avg_ptr->next;
    fast_ptr->next = *head3_ref;
 
    // Make second half circular
    *head2_ref = slow_ptr->next;
    avg_ptr->next = *head2_ref;
 
    // Make first half circular
    *head1_ref = head;
    slow_ptr->next = *head1_ref;
}
 
// Function to insert a node at
// the beginning of a Circular linked list
void push(Node** head_ref, int data)
{
    Node* ptr1 = new Node();
    Node* temp = *head_ref;
    ptr1->data = data;
    ptr1->next = *head_ref;
 
    // If linked list is not NULL then
    // set the next of last node
    if (*head_ref != NULL) {
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    }
    else
        // For the first node
        ptr1->next = ptr1;
 
    *head_ref = ptr1;
}
 
// Function to print nodes in
// a given Circular linked list
void printList(Node* head)
{
    Node* temp = head;
    if (head != NULL) {
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
    }
    cout << endl;
}
 
// Driver Code
int main()
{
    int list_size, i;
 
    // Initialize lists as empty
    Node* head = NULL;
    Node* head1 = NULL;
    Node* head2 = NULL;
    Node* head3 = NULL;
 
    // Created linked list will be
    // 1->3->5->7->9
    push(&head, 1);
    push(&head, 3);
    push(&head, 5);
    push(&head, 7);
    push(&head, 9);
 
    // Split the list
    splitList(head, &head1, &head2, &head3);
 
    // First Circular Linked List
    printList(head1);
 
    // Second Circular Linked List
    printList(head2);
 
    // Third Circular Linked List
    printList(head3);
 
    return 0;
}

// Program to split a circular linked list
// into three halves
import java.util.*;
class GFG{
 
  /* structure for a node */
  static class Node {
 
    int data;
    Node next;
  };
 
  // Function to split a list
  // (starting with head) into three lists.
  // head1_ref, head2_ref & head3_ref are
  // references to head nodes of the
  // three resultant linked lists
 
  static Node head1_ref;
  static Node head2_ref;
  static Node head3_ref;
  static void splitList(Node head)
  {
    Node slow_ptr = head;
    Node avg_ptr = head.next;
    Node fast_ptr = head.next.next;
 
    if (head == null
        || head.next == null
        || head.next.next == null)
      return;
 
    while (fast_ptr.next != head
           && fast_ptr.next.next != head) {
 
      if (fast_ptr.next.next.next
          != head)
        fast_ptr
        = fast_ptr.next.next.next;
      else {
        fast_ptr = fast_ptr.next.next;
      }
      avg_ptr = avg_ptr.next.next;
      slow_ptr = slow_ptr.next;
    }
 
    while (fast_ptr.next != head)
      fast_ptr = fast_ptr.next;
 
    // Make third half circular
    head3_ref = avg_ptr.next;
    fast_ptr.next = head3_ref;
 
    // Make second half circular
    head2_ref = slow_ptr.next;
    avg_ptr.next = head2_ref;
 
    // Make first half circular
    head1_ref = head;
    slow_ptr.next = head1_ref;
  }
 
  // Function to insert a node at
  // the beginning of a Circular linked list
  static Node push(Node head_ref, int data)
  {
    Node ptr1 = new Node();
    Node temp = head_ref;
    ptr1.data = data;
    ptr1.next = head_ref;
 
    // If linked list is not null then
    // set the next of last node
    if (head_ref != null) {
      while (temp.next != head_ref)
        temp = temp.next;
      temp.next = ptr1;
    }
    else
      // For the first node
      ptr1.next = ptr1;
 
    head_ref = ptr1;
    return head_ref;
  }
 
  // Function to print nodes in
  // a given Circular linked list
  static void printList(Node head)
  {
    Node temp = head;
    if (head != null) {
      do {
        System.out.print(temp.data+ " ");
        temp = temp.next;
      } while (temp != head);
    }
    System.out.println();
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int list_size, i;
 
    // Initialize lists as empty
    Node head = null;
    head1_ref = null;
    head2_ref = null;
    head3_ref = null;
 
    // Created linked list will be
    // 1.3.5.7.9
    head = push(head, 1);
    head = push(head, 3);
    head = push(head, 5);
    head = push(head, 7);
    head = push(head, 9);
 
    // Split the list
    splitList(head);
 
    // First Circular Linked List
    printList(head1_ref);
 
    // Second Circular Linked List
    printList(head2_ref);
 
    // Third Circular Linked List
    printList(head3_ref);
  }
}
 
// This code is contributed by shikhasingrajput

# Python code for the above approach
 
## Program to split a circular linked list
## into three halves
 
## structure for a node
class Node:
    def __init__(self, d):
        self.data = d
        self.next = None
 
class LinkedList:
 
    def __init__(self):
        self.head = None
     
    ## Function to insert a node at
    ## the beginning of a Circular linked list
    def push(self, data):
        # printList(head_ref)
        ptr1 = Node(data);
        temp = self.head
        ptr1.next = self.head
 
        ## If linked list is not None then
        ## set the next of last node
        if (self.head != None):
            while (temp.next != self.head):
                temp = temp.next;
            temp.next = ptr1
        else:
            ## For the first node
            ptr1.next = ptr1
 
        self.head = ptr1
                 
    ## Function to split a list
    ## (starting with head) into three lists.
    ## head1_ref, head2_ref & head3_ref are
    ## references to head nodes of the
    ## three resultant linked lists
    def splitList(self, llist1, llist2, llist3):
        if (self.head == None or self.head.next == None or self.head.next.next == None):
            return;
         
        slow_ptr = self.head
        avg_ptr = self.head.next
        fast_ptr = self.head.next.next
 
        while (fast_ptr.next != self.head and fast_ptr.next.next != self.head):
 
            if (fast_ptr.next.next.next != self.head):
                fast_ptr = fast_ptr.next.next.next
            else:
                fast_ptr = fast_ptr.next.next
            avg_ptr = avg_ptr.next.next
            slow_ptr = slow_ptr.next
 
        while (fast_ptr.next != self.head):
            fast_ptr = fast_ptr.next
 
        ## Make third half circular
        llist3.head = avg_ptr.next
        fast_ptr.next = llist3.head
 
        ## Make second half circular
        llist2.head = slow_ptr.next
        avg_ptr.next = llist2.head
 
        ## Make first half circular
        llist1.head = self.head
        slow_ptr.next = llist1.head
 
    ## Function to print nodes in
    ## a given Circular linked list
    def printList(self):
        temp = self.head;
        if (temp != None):
            print(temp.data, end=' ')
            temp = temp.next
            while (temp != self.head):
                print(temp.data, end=' ')
                temp = temp.next
        print("")
 
# Driver Code
if __name__=='__main__':
 
    list_size = 0
    i = 0
 
    ## Initialize lists as empty
    llist = LinkedList()
    llist1 = LinkedList()
    llist2 = LinkedList()
    llist3 = LinkedList()
 
    ## Created linked list will be
    ## 1.3.5.7.9
    llist.push(1)
    llist.push(3)
    llist.push(5)
    llist.push(7)
    llist.push(9)
 
    ## Split the list
    llist.splitList(llist1, llist2, llist3)
 
    ## First Circular Linked List
    llist1.printList()
 
    ## Second Circular Linked List
    llist2.printList()
 
    ## Third Circular Linked List
    llist3.printList()
     
     # This code is contributed by subhamgoyal2014.

9 7 
5 3 
1

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)