Рубрики

Разделить круговой связанный список на две половины

                         Original Linked List  

                         Result Linked List 1  

                         Result Linked List 2  

Если существует нечетное количество узлов , то первый список должен содержать один дополнительный.

Спасибо Geek4u за предложенный алгоритм.
1) Сохраните средний и последний указатели в круговом связанном списке, используя алгоритм черепахи и зайца.
2) Сделайте вторую половину круглой.
3) Сделать первую половину круглой.
4) Установите заголовки (или начальные) указателей двух связанных списков.

В приведенной ниже реализации, если в заданном круговом связанном списке есть нечетные узлы, то первый список результатов имеет на 1 узел больше, чем второй список результатов.

C ++

// Программа для разделения кругового связанного списка
// на две половины
#include <bits/stdc++.h>

using namespace std;

  
/ * структура для узла * /

class Node 

    public:

    int data; 

    Node *next; 

}; 

  
/ * Функция для разделения списка (начиная с заголовка)
в два списка. head1_ref и head2_ref являются
ссылки на головные узлы двух результирующих
связанные списки * /

void splitList(Node *head, Node **head1_ref,

                           Node **head2_ref) 

    Node *slow_ptr = head; 

    Node *fast_ptr = head; 

      

    if(head == NULL) 

        return

      

    / * Если в круговом списке есть нечетные узлы, то

       fast_ptr-> next становится головой и для четных узлов

       fast_ptr-> next-> next становится головой * /

    while(fast_ptr->next != head && 

          fast_ptr->next->next != head) 

    

        fast_ptr = fast_ptr->next->next; 

        slow_ptr = slow_ptr->next; 

    

      

    / * Если в списке есть четные элементы

       затем переместите fast_ptr * /

    if(fast_ptr->next->next == head) 

        fast_ptr = fast_ptr->next; 

          

    / * Установить указатель головы первой половины * /

    *head1_ref = head; 

          

    / * Установить указатель головы второй половины * /

    if(head->next != head) 

        *head2_ref = slow_ptr->next; 

          

    / * Сделать вторую полукруглую * /

    fast_ptr->next = slow_ptr->next; 

          

    / * Сделать первый полукруглый * /

    slow_ptr->next = head; 

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла в
начало Кругового связного списка * /

void push(Node **head_ref, int data) 

    Node *ptr1 = new Node();

    Node *temp = *head_ref; 

    ptr1->data = data; 

    ptr1->next = *head_ref; 

          

    / * Если связанный список не равен NULL,

       установить следующий из последнего узла * /

    if(*head_ref != NULL) 

    

        while(temp->next != *head_ref) 

        temp = temp->next;     

        temp->next = ptr1; 

    

    else

        ptr1->next = ptr1; / * Для первого узла * /

      

    *head_ref = ptr1; 

  
/ * Функция для печати узлов в
данный Круговой связанный список * /

void printList(Node *head) 

    Node *temp = head; 

    if(head != NULL) 

    

        cout << endl; 

        do

        cout << temp->data << " "

        temp = temp->next; 

        } while(temp != head); 

    

  
// Код драйвера

int main() 

    int list_size, i; 

          

    / * Инициализировать списки как пустые * /

    Node *head = NULL; 

    Node *head1 = NULL; 

    Node *head2 = NULL; 

      

    / * Созданный связанный список будет 12-> 56-> 2-> 11 * /

    push(&head, 12); 

    push(&head, 56); 

    push(&head, 2); 

    push(&head, 11); 

      

    cout << "Original Circular Linked List"

    printList(head);     

      

    / * Разделить список * /

    splitList(head, &head1, &head2); 

      

    cout << "\nFirst Circular Linked List"

    printList(head1); 

      

    cout << "\nSecond Circular Linked List"

    printList(head2); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

/ * Программа для разбиения кругового связанного списка на две половины * /
#include<stdio.h> 
#include<stdlib.h> 

  
/ * структура для узла * /

struct Node

{

  int data;

  struct Node *next;

}; 

  
/ * Функция для разделения списка (начиная с заголовка) на два списка.

   head1_ref и head2_ref являются ссылками на головные узлы

    два результирующих связанных списка * /

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;

   

  / * Если в круговом списке есть нечетные узлы, то

     fast_ptr-> next становится головой и для четных узлов

     fast_ptr-> next-> next становится головой * /

  while(fast_ptr->next != head &&

         fast_ptr->next->next != head) 

  {

     fast_ptr = fast_ptr->next->next;

     slow_ptr = slow_ptr->next;

  }  

  

 / * Если в списке есть четные элементы, переместите fast_ptr * /

  if(fast_ptr->next->next == head)

    fast_ptr = fast_ptr->next;      

    

  / * Установить указатель головы первой половины * /

  *head1_ref = head;    

       

  / * Установить указатель головы второй половины * /

  if(head->next != head)

    *head2_ref = slow_ptr->next;

    

  / * Сделать вторую полукруглую * /   

  fast_ptr->next = slow_ptr->next;

    

  / * Сделать первый полукруглый * /   

  slow_ptr->next = head;       

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция для вставки узла в начале циркуляра

   связанный список * /

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; 

    

  / * Если связанный список не равен NULL, установите следующий из

    последний узел * /

  if(*head_ref != NULL)

  {

    while(temp->next != *head_ref)

      temp = temp->next;        

    temp->next = ptr1; 

  }

  else

     ptr1->next = ptr1; / * Для первого узла * /

  

  *head_ref = ptr1;     

  
/ * Функция для печати узлов в заданном круговом связанном списке * /

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);

  }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

  int list_size, i; 

    

  / * Инициализировать списки как пустые * /

  struct Node *head = NULL;

  struct Node *head1 = NULL;

  struct Node *head2 = NULL;  

  

  / * Созданный связанный список будет 12-> 56-> 2-> 11 * /

  push(&head, 12); 

  push(&head, 56);   

  push(&head, 2);   

  push(&head, 11);   

  

  printf("Original Circular Linked List");

  printList(head);      

   

  / * Разделить список * / 

  splitList(head, &head1, &head2);

   

  printf("\nFirst Circular Linked List");

  printList(head1);  

  

  printf("\nSecond Circular Linked List");

  printList(head2);  

    

  getchar();

  return 0;

Джава

// Java-программа для удаления узла из двусвязного списка

  

class LinkedList {

  

    static Node head, head1, head2;

  

    static class Node {

  

        int data;

        Node next, prev;

  

        Node(int d) {

            data = d;

            next = prev = null;

        }

    }

  

    / * Функция для разделения списка (начиная с заголовка) на два списка.

     head1_ref и head2_ref являются ссылками на головные узлы

     два результирующих связанных списка * /

    void splitList() {

        Node slow_ptr = head;

        Node fast_ptr = head;

  

        if (head == null) {

            return;

        }

  

        / * Если в круговом списке есть нечетные узлы, то

         fast_ptr-> next становится головой и для четных узлов

         fast_ptr-> next-> next становится головой * /

        while (fast_ptr.next != head

                && fast_ptr.next.next != head) {

            fast_ptr = fast_ptr.next.next;

            slow_ptr = slow_ptr.next;

        }

  

        / * Если в списке есть четные элементы, переместите fast_ptr * /

        if (fast_ptr.next.next == head) {

            fast_ptr = fast_ptr.next;

        }

  

        / * Установить указатель головы первой половины * /

        head1 = head;

  

        / * Установить указатель головы второй половины * /

        if (head.next != head) {

            head2 = slow_ptr.next;

        }

        / * Сделать вторую полукруглую * /

        fast_ptr.next = slow_ptr.next;

  

        / * Сделать первый полукруглый * /

        slow_ptr.next = head;

    }

  

    / * Функция для печати узлов в заданном односвязном списке * /

    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();

  

        // Созданный связанный список будет 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);

  

        // Разделить список

        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);

          

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

# Программа Python для разделения кругового связанного списка на две половины

  
# Структура узла

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

  
# Класс для создания нового кругового связанного списка

class CircularLinkedList:

      

    # Конструктор для создания пустого кругового связанного списка

    def __init__(self):

        self.head = None

  

    # Функция для вставки узла в начале

    # круговой связанный список

    def push(self, data):

        ptr1 = Node(data)

        temp = self.head

          

        ptr1.next = self.head

  

        # Если связанный список не None, тогда установите следующий из

        # последний узел

        if self.head is not None:

            while(temp.next != self.head):

                temp = temp.next 

            temp.next = ptr1

  

        else:

            ptr1.next = ptr1 # Для первого узла

  

        self.head = ptr1 

  

    # Функция для печати узлов в заданном круговом связанном списке

    def printList(self):

        temp = self.head

        if self.head is not None:

            while(True):

                print "%d" %(temp.data),

                temp = temp.next

                if (temp == self.head):

                    break 

  

  

    # Функция для разделения списка (начиная с заголовка) на

    # два списка. head1 и head2 являются головными узлами

    # два результирующих связанных списка

    def splitList(self, head1, head2):

        slow_ptr = self.head 

        fast_ptr = self.head

      

        if self.head is None:

            return 

          

        # Если здесь нечетные узлы в круговом списке, то

        # fast_ptr-> next становится головой и для четных узлов

        # fast_ptr-> next-> next становится головой

        while(fast_ptr.next != self.head and 

            fast_ptr.next.next != self.head ):

            fast_ptr = fast_ptr.next.next

            slow_ptr = slow_ptr.next

  

        # Если в списке есть элементы событий,

        # move fast_ptr

        if fast_ptr.next.next == self.head:

            fast_ptr = fast_ptr.next

  

        # Установить указатель головы первой половины

        head1.head = self.head

  

        # Установить указатель головы второй половины

        if self.head.next != self.head:

            head2.head = slow_ptr.next

  

        # Сделайте вторую половину круглой

        fast_ptr.next = slow_ptr.next

      

        # Сделать первую половину круглой

        slow_ptr.next = self.head

  

  
# Драйверная программа для проверки вышеуказанных функций

  
# Инициализировать списки как пустые

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()

  
# Разделить список
head.splitList(head1 , head2)

  

print "\nFirst Circular Linked List"

head1.printList()

  

print "\nSecond Circular Linked List"

head2.printList()

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для удаления узла
// из двусвязного списка

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;

        }

    }

  

    / * Функция для разделения списка (начиная с заголовка)

    в два списка. head1_ref и head2_ref являются

    ссылки на головные узлы двух

    результирующие связанные списки * /

    void splitList() 

    {

        Node slow_ptr = head;

        Node fast_ptr = head;

  

        if (head == null)

        {

            return;

        }

  

        / * Если в

        круговой список затем fast_ptr-> следующий

        становится головой и для четных узлов

        fast_ptr-> next-> next становится головой * /

        while (fast_ptr.next != head &&

               fast_ptr.next.next != head)

        {

            fast_ptr = fast_ptr.next.next;

            slow_ptr = slow_ptr.next;

        }

  

        / * Если в списке есть четные элементы

           затем переместите fast_ptr * /

        if (fast_ptr.next.next == head)

        {

            fast_ptr = fast_ptr.next;

        }

  

        / * Установить указатель головы первой половины * /

        head1 = head;

  

        / * Установить указатель головы второй половины * /

        if (head.next != head)

        {

            head2 = slow_ptr.next;

        }

          

        / * Сделать вторую полукруглую * /

        fast_ptr.next = slow_ptr.next;

  

        / * Сделать первый полукруглый * /

        slow_ptr.next = head;

    }

  

    / * Функция для печати узлов

    в данном односвязном списке * /

    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();

  

        // Созданный связанный список будет 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);

  

        // Разделить список

        list.splitList();

        Console.WriteLine("");

        Console.WriteLine("First Circular List ");

        list.printList(list.head1);

        Console.WriteLine("");

        Console.WriteLine("Second Circular List ");

        list.printList(list.head2);

    }

}

  
// Этот код предоставлен PrinciRaj1992

Выход:

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

Сложность времени: O (n)

Пожалуйста, напишите комментарии, если вы обнаружите какую-либо ошибку в приведенном выше коде / алгоритме, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Разделить круговой связанный список на две половины

0.00 (0%) 0 votes