Рубрики

Повернуть связанный список

Получив односвязный список, поверните связанный список против часовой стрелки на k узлов. Где k — данное положительное целое число. Например, если данный связанный список 10-> 20-> 30-> 40-> 50-> 60 и k равен 4, список следует изменить на 50-> 60-> 10-> 20-> 30- > 40. Предположим, что k меньше, чем количество узлов в связанном списке.

Чтобы повернуть связанный список, нам нужно изменить следующий из k-го узла на NULL, следующий за последним узлом к предыдущему главному узлу и, наконец, изменить заголовок на (k + 1) -й узел. Таким образом, нам нужно получить три узла: k-й узел, (k + 1) -й узел и последний узел.
Пройдите по списку с начала и остановитесь на k-м узле. Сохранить указатель на k-й узел. Мы можем получить (k + 1) -й узел, используя kthNode-> next. Продолжайте обход до конца и сохраняйте указатель на последний узел. Наконец, измените указатели, как указано выше.

На рисунке ниже показано, как работает функция поворота в коде:

C ++

// C ++ программа для вращения
// связанный список против часовой стрелки

  
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

class Node 

    public:

    int data; 

    Node* next; 

}; 

  
// Эта функция вращает связанный список
// против часовой стрелки и обновляет
// голова. Функция предполагает, что к
// меньше размера связанного списка.
// не меняет список, если
// k больше или равно размеру

void rotate(Node **head_ref, int k) 

    if (k == 0) 

    return

  

    // Давайте поймем ниже

    // код для примера k = 4 и

    // list = 10-> 20-> 30-> 40-> 50-> 60.

    Node* current = *head_ref; 

  

    // текущий будет указывать на

    // kth или NULL после этого цикла.

    // текущий будет указывать на узел

    // 40 в приведенном выше примере

    int count = 1; 

    while (count < k && current != NULL) 

    

        current = current->next; 

        count++; 

    

  

    // Если ток равен NULL, k больше чем

    // или равно количеству узлов в связанном списке.

    // Не меняйте список в этом случае

    if (current == NULL) 

        return

  

    // текущие точки на k-й узел.

    // Сохраняем его в переменной. kthNode

    // указывает на узел 40 в приведенном выше примере

    Node *kthNode = current; 

  

    // текущий будет указывать на

    // последний узел после этого цикла

    // текущий будет указывать на

    // узел 60 в приведенном выше примере

    while (current->next != NULL) 

        current = current->next; 

  

    // Меняем следующий последний узел на предыдущий

    // Следующее из 60 теперь изменено на узел 10

    current->next = *head_ref; 

  

    // Изменить голову на (k + 1) -й узел

    // голова теперь изменена на узел 50

    *head_ref = kthNode->next; 

  

    // изменить следующий узел k на NULL

    // следующий из 40 теперь NULL

    kthNode->next = NULL; 

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция подтолкнуть узел * /

void push (Node** head_ref, int new_data) 

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref); 

  

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

    (*head_ref) = new_node; 

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

void printList(Node *node) 

    while (node != NULL) 

    

        cout << node->data << " "

        node = node->next; 

    

  
/ * Код водителя * /

int main(void

    / * Начнем с пустого списка * /

    Node* head = NULL; 

  

    // создаем список 10-> 20-> 30-> 40-> 50-> 60

    for (int i = 60; i > 0; i -= 10) 

        push(&head, i); 

  

    cout << "Given linked list \n"

    printList(head); 

    rotate(&head, 4); 

  

    cout << "\nRotated Linked list \n"

    printList(head); 

  

    return (0); 

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

С

// C программа для вращения связанного списка против часовой стрелки

  
#include<stdio.h>
#include<stdlib.h>

  
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

  
// Эта функция вращает связанный список против часовой стрелки и
// обновляет голову. Функция предполагает, что k меньше
// чем размер связанного списка. Это не изменяет список, если
// k больше или равно размеру

void rotate(struct Node **head_ref, int k)

{

     if (k == 0)

       return;

  

    // Давайте разберемся в приведенном ниже коде для примера k = 4 и

    // list = 10-> 20-> 30-> 40-> 50-> 60.

    struct Node* current = *head_ref;

  

    // current будет указывать на kth или NULL после этого цикла.

    // текущий будет указывать на узел 40 в приведенном выше примере

    int count = 1;

    while (count < k && current != NULL)

    {

        current = current->next;

        count++;

    }

  

    // Если ток равен NULL, k больше или равно количеству

    // узлов в связанном списке. Не меняйте список в этом случае

    if (current == NULL)

        return;

  

    // текущие точки на k-й узел. Сохраните это в переменной.

    // kthNode указывает на узел 40 в приведенном выше примере

    struct Node *kthNode = current;

  

    // текущий будет указывать на последний узел после этого цикла

    // текущий будет указывать на узел 60 в приведенном выше примере

    while (current->next != NULL)

        current = current->next;

  

    // Меняем следующий последний узел на предыдущий

    // Следующее из 60 теперь изменено на узел 10

    current->next = *head_ref;

  

    // Изменить голову на (k + 1) -й узел

    // голова теперь изменена на узел 50

    *head_ref = kthNode->next;

  

    // изменить следующий узел k на NULL

    // следующий из 40 теперь NULL

    kthNode->next = NULL;

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция подтолкнуть узел * /

void push (struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node =

        (struct Node*) malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data  = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

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

    (*head_ref)    = new_node;

}

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

void printList(struct Node *node)

{

    while (node != NULL)

    {

        printf("%d ", node->data);

        node = node->next;

    }

}

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

int main(void)

{

    / * Начнем с пустого списка * /

    struct Node* head = NULL;

  

    // создаем список 10-> 20-> 30-> 40-> 50-> 60

    for (int i = 60; i > 0; i -= 10)

        push(&head, i);

  

    printf("Given linked list \n");

    printList(head);

    rotate(&head, 4);

  

    printf("\nRotated Linked list \n");

    printList(head);

  

    return (0);

}

Джава

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

  

class LinkedList

{

    Node head;  // заголовок списка

  

    / * Узел связанного списка * /

    class Node

    {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Эта функция вращает связанный список против часовой стрелки

    // и обновляет голову. Функция предполагает, что к

    // меньше размера связанного списка. Не меняет

    // список, если k больше или равно размеру

    void rotate(int k)

    {

        if (k == 0) return;

  

        // Давайте разберемся в приведенном ниже коде, например, k = 4

        // и list = 10-> 20-> 30-> 40-> 50-> 60.

        Node current  = head;

  

        // текущий будет указывать на kth или NULL после этого

        // цикл. ток будет указывать на узел 40 в приведенном выше примере

        int count = 1;

        while (count < k && current !=  null)

        {

            current = current.next;

            count++;

        }

  

        // Если ток равен NULL, k больше или равно количеству

        // узлов в связанном списке. Не меняйте список в этом случае

        if (current == null)

            return;

  

        // текущие точки на k-й узел. Сохраните это в переменной.

        // kthNode указывает на узел 40 в приведенном выше примере

        Node kthNode = current;

  

        // текущий будет указывать на последний узел после этого цикла

        // текущий будет указывать на узел 60 в приведенном выше примере

        while (current.next != null)

            current = current.next;

  

        // Меняем следующий последний узел на предыдущий

        // Следующее из 60 теперь изменено на узел 10

  

        current.next = head;

  

        // Изменить голову на (k + 1) -й узел

        // голова теперь изменена на узел 50

        head = kthNode.next;

  

        // изменить следующий из k-го узла на ноль

        kthNode.next = null;

  

    }

  

    / * Дана ссылка (указатель на указатель) на голову

        списка и int, нажмите новый узел на передней панели

        из списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    void printList()

    {

        Node temp = head;

        while(temp != null)

        {

            System.out.print(temp.data+" ");

            temp = temp.next;

        }

        System.out.println();

    }

  

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

    public static void main(String args[])

    {

        LinkedList llist = new LinkedList();

  

        // создаем список 10-> 20-> 30-> 40-> 50-> 60

        for (int i = 60; i >= 10; i -= 10)

            llist.push(i);

  

        System.out.println("Given list");

        llist.printList();

  

        llist.rotate(4);

  

        System.out.println("Rotated Linked List");

        llist.printList();

    }

} / * Этот код предоставлен Раджатом Мишрой * /

питон

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

  
# Класс узла

class Node:

  

    # Конструктор для инициализации объекта узла

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

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

    def push(self, new_data):

        # выделить узел и поместить данные

        new_node = Node(new_data)

  

        # Сделать следующий из нового узла в качестве головы

        new_node.next = self.head

          

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

        self.head = new_node

  

    # Сервисная функция, чтобы напечатать это связанный LinkedList

    def printList(self):

        temp = self.head

        while(temp):

            print temp.data,

            temp = temp.next

  

    # Эта функция вращает связанный список против часовой стрелки и

    # обновляет голову. Функция предполагает, что k меньше

    # чем размер связанного списка. Это не изменяет список, если

    # k больше чем равно размеру

    def rotate(self, k):

        if k == 0

            return 

          

        # Давайте разберемся в приведенном ниже коде, например, k = 4

        # и список = 10-> 20-> 30-> 40-> 50-> 60

        current = self.head

          

        # current будет указывать на kth или NULL после

        # этот цикл

        # current будет указывать на узел 40 в приведенном выше примере

        count = 1 

        while(count <k and current is not None):

            current = current.next

            count += 1

      

        # Если ток равен None, k больше или равно

        # количество узлов в связанном списке. Не меняй

        # список в этом случае

        if current is None:

            return

  

        # текущий указывает на k-й узел. Сохраните это в переменной

        # k-й узел указывает на узел 40 в приведенном выше примере

        kthNode = current 

      

        # current будет указывать на узел lsat после этого цикла

        # current будет указывать на узел 60 в примере выше

        while(current.next is not None):

            current = current.next

  

        # Изменить следующий последний узел на предыдущий заголовок

        # Следующее из 60 теперь изменено на узел 10

        current.next = self.head

          

        # Изменить голову на (k + 1) -й узел

        # голова не изменена на узел 50

        self.head = kthNode.next

  

        # изменить следующий из k-го узла на NULL

        # следующий из 40 не NULL

        kthNode.next = None

  

  

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

llist = LinkedList()

  
# Создайте список 10-> 20-> 30-> 40-> 50-> 60

for i in range(60, 0, -10):

    llist.push(i)

  

print "Given linked list"

llist.printList()

llist.rotate(4)

  

print "\nRotated Linked list"

llist.printList()

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

C #

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

using System;

  

public class LinkedList

{

    Node head; // заголовок списка

  

    / * Узел связанного списка * /

    public class Node

    {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Эта функция вращает связанный список

    // против часовой стрелки и обновляет голову.

    // Функция предполагает, что k меньше

    // чем размер связанного списка. Не меняет

    // список, если k больше или равно размеру

    void rotate(int k)

    {

        if (k == 0) return;

  

        // Давайте поймем ниже

        // код для примера k = 4

        // и list = 10-> 20-> 30-> 40-> 50-> 60.

        Node current = head;

  

        // текущий будет указывать на kth

        // или NULL после этого цикла. текущий

        // будет указывать на узел 40 в приведенном выше примере

        int count = 1;

        while (count < k && current != null)

        {

            current = current.next;

            count++;

        }

  

        // Если ток равен NULL, k больше чем

        // или равно количеству узлов в связанном списке.

        // Не меняйте список в этом случае

        if (current == null)

            return;

  

        // текущие точки на k-й узел.

        // Сохраняем его в переменной.

        // kthNode указывает на узел

        // 40 в приведенном выше примере

        Node kthNode = current;

  

        // текущий будет указывать на

        // последний узел после этого цикла

        // текущий будет указывать на

        // узел 60 в приведенном выше примере

        while (current.next != null)

            current = current.next;

  

        // Меняем следующий последний узел на предыдущий

        // Следующее из 60 теперь изменено на узел 10

  

        current.next = head;

  

        // Изменить голову на (k + 1) -й узел

        // голова теперь изменена на узел 50

        head = kthNode.next;

  

        // изменить следующий из k-го узла на ноль

        kthNode.next = null;

  

    }

  

    / * Дана ссылка (указатель на указатель) на голову

        списка и int, нажмите новый узел на передней панели

        из списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    void printList()

    {

        Node temp = head;

        while(temp != null)

        {

            Console.Write(temp.data+" ");

            temp = temp.next;

        }

        Console.WriteLine();

    }

  

    / * Код водителя * /

    public static void Main()

    {

        LinkedList llist = new LinkedList();

  

        // создаем список 10-> 20-> 30-> 40-> 50-> 60

        for (int i = 60; i >= 10; i -= 10)

            llist.push(i);

  

        Console.WriteLine("Given list");

        llist.printList();

  

        llist.rotate(4);

  

        Console.WriteLine("Rotated Linked List");

        llist.printList();

    }

}

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


Выход:

Given linked list
10  20  30  40  50  60
Rotated Linked list
50  60  10  20  30  40

Сложность времени: O (n), где n — количество узлов в связанном списке. Код пересекает связанный список только один раз.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Повернуть связанный список

0.00 (0%) 0 votes