Dividir una lista enlazada circular en dos mitades

                         Original Linked List  

                         Result Linked List 1  

                         Result Linked List 2  

Si hay un número impar de Nodes , la primera lista debe contener uno adicional.
 

Complete Interview Preparation - GFG

Gracias a Geek4u por sugerir el algoritmo. 
1) Almacene los punteros medio y último de la lista enlazada circular utilizando el algoritmo de Turtle y liebre. 
2) Hacer la segunda mitad circular. 
3) Hacer la primera mitad circular. 
4) Establecer punteros de cabeza (o inicio) de las dos listas enlazadas.
En la implementación a continuación, si hay Nodes impares en la lista enlazada circular dada, la primera lista de resultados tiene 1 Node más que la segunda lista de resultados. 
 

C++

// Program to split a circular linked list
// into two 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 two lists. head1_ref and head2_ref are 
references to head nodes of the two resultant 
linked lists */
void splitList(Node *head, Node **head1_ref,
                           Node **head2_ref) 
{ 
    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_ref = head; 
          
    /* Set the head pointer of second half */
    if(head->next != head) 
        *head2_ref = slow_ptr->next; 
          
    /* Make second half circular */
    fast_ptr->next = slow_ptr->next; 
          
    /* Make first half circular */
    slow_ptr->next = head; 
} 
  
/* UTILITY FUNCTIONS */
/* 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
        ptr1->next = ptr1; /*For the first node */
      
    *head_ref = ptr1; 
} 
  
/* Function to print nodes in 
a given Circular linked list */
void printList(Node *head) 
{ 
    Node *temp = head; 
    if(head != NULL) 
    { 
        cout << endl; 
        do { 
        cout << temp->data << " "; 
        temp = temp->next; 
        } while(temp != head); 
    } 
} 
  
// Driver Code
int main() 
{ 
    int list_size, i; 
          
    /* Initialize lists as empty */
    Node *head = NULL; 
    Node *head1 = NULL; 
    Node *head2 = NULL; 
      
    /* Created linked list will be 12->56->2->11 */
    push(&head, 12); 
    push(&head, 56); 
    push(&head, 2); 
    push(&head, 11); 
      
    cout << "Original Circular Linked List"; 
    printList(head);     
      
    /* Split the list */
    splitList(head, &head1, &head2); 
      
    cout << "\nFirst Circular Linked List"; 
    printList(head1); 
      
    cout << "\nSecond Circular Linked List"; 
    printList(head2); 
    return 0; 
} 
  
// This code is contributed by rathbhupendra

C

/* Program to split a circular linked list into two halves */
#include<stdio.h> 
#include<stdlib.h> 
  
/* structure for a node */
struct Node
{
  int data;
  struct Node *next;
}; 
  
/* 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(struct Node *head, struct Node **head1_ref, 
                                            struct Node **head2_ref)
{
  struct Node *slow_ptr = head;
  struct 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_ref = head;    
       
  /* Set the head pointer of second half */
  if(head->next != head)
    *head2_ref = slow_ptr->next;
    
  /* Make second half circular */   
  fast_ptr->next = slow_ptr->next;
    
  /* Make first half circular */   
  slow_ptr->next = head;       
}
  
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of a Circular 
   linked list */
void push(struct Node **head_ref, int data)
{
  struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
  struct 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
     ptr1->next = ptr1; /*For the first node */
  
  *head_ref = ptr1;     
} 
  
/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
  struct Node *temp = head; 
  if(head != NULL)
  {
    printf("\n");
    do {
      printf("%d ", temp->data);
      temp = temp->next;
    } while(temp != head);
  }
}
  
/* Driver program to test above functions */
int main()
{
  int list_size, i; 
    
  /* Initialize lists as empty */
  struct Node *head = NULL;
  struct Node *head1 = NULL;
  struct Node *head2 = NULL;  
  
  /* Created linked list will be 12->56->2->11 */
  push(&head, 12); 
  push(&head, 56);   
  push(&head, 2);   
  push(&head, 11);   
  
  printf("Original Circular Linked List");
  printList(head);      
   
  /* Split the list */ 
  splitList(head, &head1, &head2);
   
  printf("\nFirst Circular Linked List");
  printList(head1);  
  
  printf("\nSecond Circular Linked List");
  printList(head2);  
    
  getchar();
  return 0;
} 

Java

// 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);
          
    }
}
  
// This code has been contributed by Mayank Jaiswal

Python3

# Python program to split circular linked list into two halves
  
# A node structure
class Node:
      
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.next = None
  
  
# Class to create a new  Circular Linked list
class CircularLinkedList:
      
    # Constructor to create a empty circular linked list
    def __init__(self):
        self.head = None
  
    # Function to insert a node at the beginning of a
    # circular linked list
    def push(self, data):
        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 is not None:
            while(temp.next != self.head):
                temp = temp.next 
            temp.next = ptr1
  
        else:
            ptr1.next = ptr1 # For the first node
  
        self.head = ptr1 
  
    # Function to print nodes in a given circular linked list
    def printList(self):
        temp = self.head
        if self.head is not None:
            while(True):
                print ("%d" %(temp.data),end=' ')
                temp = temp.next
                if (temp == self.head):
                    break 
  
  
    # Function to split a list (starting with head) into 
    # two lists. head1 and head2 are the head nodes of the
    # two resultant linked lists
    def splitList(self, head1, head2):
        slow_ptr = self.head 
        fast_ptr = self.head
      
        if self.head is None:
            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 != self.head and 
            fast_ptr.next.next != self.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 == self.head:
            fast_ptr = fast_ptr.next
  
        # Set the head pointer of first half
        head1.head = self.head
  
        # Set the head pointer of second half
        if self.head.next != self.head:
            head2.head = slow_ptr.next
  
        # Make second half circular
        fast_ptr.next = slow_ptr.next
      
        # Make first half circular
        slow_ptr.next = self.head
  
  
# Driver program to test above functions
  
# Initialize lists as empty
head = CircularLinkedList() 
head1 = CircularLinkedList()
head2 = CircularLinkedList()
  
head.push(12)
head.push(56)
head.push(2)
head.push(11)
  
print ("Original Circular Linked List")
head.printList()
  
# Split the list 
head.splitList(head1 , head2)
  
print ("\nFirst Circular Linked List")
head1.printList()
  
print ("\nSecond Circular Linked List")
head2.printList()
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to delete a node
// from doubly linked list
using System;
class GFG
{
    public Node head, head1, head2;
  
    public class Node 
    {
        public int data;
        public Node next, prev;
  
        public 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
            {
                Console.Write(temp.data + " ");
                temp = temp.next;
            } while (temp != node);
        }
    }
  
    public static void Main(String[] args)
    {
        GFG list = new GFG();
  
        // 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;
  
        Console.WriteLine("Original Circular Linked list ");
        list.printList(list.head);
  
        // Split the list
        list.splitList();
        Console.WriteLine("");
        Console.WriteLine("First Circular List ");
        list.printList(list.head1);
        Console.WriteLine("");
        Console.WriteLine("Second Circular List ");
        list.printList(list.head2);
    }
}
  
// This code is contributed by PrinciRaj1992

Javascript

<script>
  
class Node
{
    constructor(d)
    {
        this.data = d;
        this.next = this.prev = null;
    }
}
  
let head, head1, head2;
  
function splitList()
{
    let slow_ptr = head;
        let 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 */
    function printList(node) {
        let temp = node;
        if (node != null) {
            do {
                document.write(temp.data + " ");
                temp = temp.next;
            } while (temp != node);
        }
        }
  
  
  
    
//Created linked list will be 12->56->2->11
head = new Node(12);
head.next = new Node(56);
head.next.next = new Node(2);
head.next.next.next = new Node(11);
head.next.next.next.next = head;
  
document.write("Original Circular Linked list <br>");
printList(head);
  
// Split the list
splitList();
document.write("<br>");
document.write("First Circular List <br>");
printList(head1);
document.write("<br>");
document.write("Second Circular List <br>");
printList(head2);
  
  
// This code is contributed by avanitrachhadiya2155
</script>

Producción: 
 

Original Circular Linked List
11 2 56 12 
First Circular Linked List
11 2 
Second Circular Linked List
56 12 

Complejidad de tiempo: O(n) Como solo nos estamos moviendo una vez a través de la lista

Espacio auxiliar: O(1) Como no se usa espacio adicional,
escriba comentarios si encuentra algún error en el código/algoritmo anterior, o encuentre otras formas de resolver el mismo problema
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *