Рубрики

Обратные чередующиеся узлы K в односвязном списке

При наличии связанного списка напишите функцию, которая будет эффективно переворачивать каждые чередующиеся k узлов (где k является входом в функцию). Дайте сложность вашего алгоритма.

Пример:

Inputs:   1->2->3->4->5->6->7->8->9->NULL and k = 3
Output:   3->2->1->4->5->6->9->8->7->NULL. 

Метод 1 (Обработка 2k узлов и рекурсивный вызов для остальной части списка)
Этот метод является в основном продолжением метода, обсуждаемого в этом посте.

kAltReverse(struct node *head, int k)
  1)  Reverse first k nodes.
  2)  In the modified list head points to the kth node.  So change next 
       of head to (k+1)th node
  3)  Move the current pointer to skip next k nodes.
  4)  Call the kAltReverse() recursively for rest of the n - 2k nodes.
  5)  Return new head of the list.

C ++

// C ++ программа для обратного чередования
// k узлов в связанном списке
#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node* next; 

}; 

  
/ * Инвертирует альтернативные k узлов и
возвращает указатель на новый головной узел * /

Node *kAltReverse(Node *head, int k) 

    Node* current = head; 

    Node* next; 

    Node* prev = NULL; 

    int count = 0; 

  

    / * 1) поменять местами первые k узлов связного списка * /

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

    

    next = current->next; 

    current->next = prev; 

    prev = current; 

    current = next; 

    count++; 

    

      

    / * 2) Теперь голова указывает на k-й узел.

    Так что поменяйте следующую голову на (k + 1) -й узел * /

    if(head != NULL) 

    head->next = current; 

  

    / * 3) Мы не хотим менять следующий k

       узлы. Так двигай ток

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

    count = 0; 

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

    

    current = current->next; 

    count++; 

    

  

    / * 4) Рекурсивно вызывать список

    начиная с текущего-> далее. И сделать

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

    if(current != NULL) 

    current->next = kAltReverse(current->next, k); 

  

    / * 5) предыдущая глава списка ввода * /

    return prev; 

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

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) 

    int count = 0; 

    while(node != NULL) 

    

        cout<<node->data<<" "

        node = node->next; 

        count++; 

    

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

int main(void

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

    Node* head = NULL; 

    int i; 

      

    // создаем список 1-> 2-> 3-> 4-> 5 ...... -> 20

    for(i = 20; i > 0; i--) 

    push(&head, i); 

  

    cout<<"Given linked list \n"

    printList(head); 

    head = kAltReverse(head, 3); 

  

    cout<<"\n Modified Linked list \n"

    printList(head); 

    return(0); 

  

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

С

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

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

struct Node

{

    int data;

    struct Node* next;

};

  
/ * Инвертирует альтернативные k узлов и

   возвращает указатель на новый головной узел * /

struct Node *kAltReverse(struct Node *head, int k)

{

    struct Node* current = head;

    struct Node* next;

    struct Node* prev = NULL;

    int count = 0;   

  

    / * 1) поменять местами первые k узлов связного списка * /

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

    {

       next  = current->next;

       current->next = prev;

       prev = current;

       current = next;

       count++;

    }

    

    / * 2) Теперь голова указывает на k-й узел. Так что меняй дальше

       головы до (k + 1) -ого узла * / 

    if(head != NULL)

      head->next = current;   

  

    / * 3) Мы не хотим возвращать следующие k узлов. Так двигай ток

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

    count = 0;

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

    {

      current = current->next;

      count++;

    }

  

    / * 4) Рекурсивно вызывать список, начиная с текущего-> следующего.

       И сделать остальную часть списка следующим за первым узлом * /

    if(current !=  NULL)

       current->next = kAltReverse(current->next, k); 

  

    / * 5) предыдущая глава списка ввода * /

    return prev;

}

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

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)

{

    int count = 0;

    while(node != NULL)

    {

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

        node = node->next;

        count++;

    }

}    

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

int main(void)

{

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

    struct Node* head = NULL;

    int i;

    // создаем список 1-> 2-> 3-> 4-> 5 ...... -> 20

    for(i = 20; i > 0; i--)

      push(&head, i);

  

     printf("\n Given linked list \n");

     printList(head);

     head = kAltReverse(head, 3);

  

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

     printList(head);

  

     getchar();

     return(0);

}

Джава

// Java программа для обратного чередования k узлов в связанном списке

  

class LinkedList {

  

    static Node head;

  

    class Node {

  

        int data;

        Node next;

  

        Node(int d) {

            data = d;

            next = null;

        }

    }

  

    / * Инвертирует альтернативные k узлов и

     возвращает указатель на новый головной узел * /

    Node kAltReverse(Node node, int k) {

        Node current = node;

        Node next = null, prev = null;

        int count = 0;

  

        / * 1) поменять местами первые k узлов связного списка * /

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

            next = current.next;

            current.next = prev;

            prev = current;

            current = next;

            count++;

        }

  

        / * 2) Теперь голова указывает на k-й узел. Так что меняй дальше

         головы до (k + 1) -ого узла * /

        if (node != null) {

            node.next = current;

        }

  

        / * 3) Мы не хотим возвращать следующие k узлов. Так двигай ток

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

        count = 0;

        while (count < k - 1 && current != null) {

            current = current.next;

            count++;

        }

  

        / * 4) Рекурсивно вызывать список, начиная с текущего-> следующего.

         И сделать остальную часть списка следующим за первым узлом * /

        if (current != null) {

            current.next = kAltReverse(current.next, k);

        }

  

        / * 5) предыдущая глава списка ввода * /

        return prev;

    }

  

    void printList(Node node) {

        while (node != null) {

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

            node = node.next;

        }

    }

  

    void push(int newdata) {

        Node mynode = new Node(newdata);

        mynode.next = head;

        head = mynode;

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

  

        // Создание связанного списка

        for (int i = 20; i > 0; i--) {

            list.push(i);

        }

        System.out.println("Given Linked List :");

        list.printList(head);

        head = list.kAltReverse(head, 3);

        System.out.println("");

        System.out.println("Modified Linked List :");

        list.printList(head);

  

    }

}

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

python3

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

import math

  
# Узел списка ссылок

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.next = None

  
# Обращает чередующиеся k узлов и
# возвращает пера в новый головной узел

def kAltReverse(head, k) : 

    current = head 

    next = None

    prev = None

    count = 0

  

    # 1) поменять местами первые k узлов связанного списка

    while (current != None and count < k) : 

        next = current.next

        current.next = prev 

        prev = current 

        current = next

        count = count + 1;

      

    # 2) Теперь отправляйтесь по pos к k-му узлу.

    # Так что поменяйте следующую голову на (k + 1) -й узел

    if(head != None): 

        head.next = current 

  

    # 3) Мы не хотим менять следующий k

    # узлы. Так двигай ток

    # Пропустить следующие k узлов

    count = 0

    while(count < k - 1 and current != None ): 

        current = current.next

        count = count + 1

      

    # 4) Рекурсивно вызывать список

    # начиная с current.next. И сделать

    # остаток списка как следующий из первого узла

    if(current != None): 

        current.next = kAltReverse(current.next, k) 

  

    # 5) предыдущая глава списка ввода

    return prev 

  
# ПОЛЕЗНЫЕ ФУНКЦИИ
# Функция нажать на узел

def push(head_ref, new_data): 

      

    # выделить узел

    new_node = Node(new_data)

  

    # положить в данные

    # new_node.data = new_data

  

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

    new_node.next = head_ref 

  

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

    head_ref = new_node

      

    return head_ref

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

def prList(node): 

    count = 0

    while(node != None): 

        print(node.data, end = " "

        node = node.next

        count = count + 1

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

if __name__=='__main__':

      

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

    head = None

  

    # создать список 1.2.3.4.5 ...... .20

    for i in range(20, 0, -1):

        head = push(head, i) 

          

    print("Given linked list "

    prList(head) 

    head = kAltReverse(head, 3

  

    print("\nModified Linked list"

    prList(head) 

      
# Этот код предоставлен Srathore

C #

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

using System;

class LinkedList 

  

    static Node head; 

  

    public class Node 

    

  

        public int data; 

        public Node next; 

  

        public Node(int d)

        

            data = d; 

            next = null

        

    

  

    / * Инвертирует альтернативные k узлов и

    возвращает указатель на новый головной узел * /

    Node kAltReverse(Node node, int k) 

    

        Node current = node; 

        Node next = null, prev = null

        int count = 0; 

  

        / * 1) поменять местами первые k узлов связного списка * /

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

        

            next = current.next; 

            current.next = prev; 

            prev = current; 

            current = next; 

            count++; 

        

  

        / * 2) Теперь голова указывает на kth

        узел. Так что меняй дальше

        головы до (k + 1) -ого узла * /

        if (node != null

        

            node.next = current; 

        

  

        / * 3) Мы не хотим повернуть вспять

        следующие k узлов. Так двигай ток

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

        count = 0; 

        while (count < k - 1 && current != null

        

            current = current.next; 

            count++; 

        

  

        / * 4) Рекурсивно вызывать для

        список, начиная с текущего-> следующий.

        И сделать остальную часть списка как

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

        if (current != null)

        

            current.next = kAltReverse(current.next, k); 

        

  

        / * 5) предыдущая глава списка ввода * /

        return prev; 

    

  

    void printList(Node node) 

    

        while (node != null

        

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

            node = node.next; 

        

    

  

    void push(int newdata)

    

        Node mynode = new Node(newdata); 

        mynode.next = head; 

        head = mynode; 

    

  

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

    public static void Main(String []args)

    

        LinkedList list = new LinkedList(); 

  

        // Создание связанного списка

        for (int i = 20; i > 0; i--) 

        

            list.push(i); 

        

        Console.WriteLine("Given Linked List :"); 

        list.printList(head); 

        head = list.kAltReverse(head, 3); 

        Console.WriteLine(""); 

        Console.WriteLine("Modified Linked List :"); 

        list.printList(head); 

    

  
// Этот код предоставлен Арнабом Кунду

Выход:

Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Modified Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

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

Метод 2 (Обработка k узлов и рекурсивный вызов для остальной части списка)
Метод 1 реверсирует первый k узел и затем перемещает указатель на k узлов вперед. Таким образом, метод 1 использует два цикла while и обрабатывает 2k узлов за один рекурсивный вызов.
Этот метод обрабатывает только k узлов в рекурсивном вызове. Он использует третий параметр bool b, который решает, следует ли обратить k элементов или просто переместить указатель.

_kAltReverse(struct node *head, int k, bool b)
  1)  If b is true, then reverse first k nodes.
  2)  If b is false, then move the pointer k nodes ahead.
  3)  Call the kAltReverse() recursively for rest of the n - k nodes and link 
       rest of the modified list with end of first k nodes. 
  4)  Return new head of the list.

C ++

#include <bits/stdc++.h>

using namespace std;

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

class node 

    public:

    int data; 

    node* next; 

}; 

  
/ * Вспомогательная функция для kAltReverse () * /

node * _kAltReverse(node *node, int k, bool b); 

  
/ * В качестве альтернативы переворачивает данный связанный список
в группах заданного размера к. * /

node *kAltReverse(node *head, int k) 

    return _kAltReverse(head, k, true); 

  
/ * Вспомогательная функция для kAltReverse ().
Он переворачивает k узлов списка, только если
третий параметр b передается как true,
в противном случае перемещает указатель на k узлов вперед
и рекурсивно вызывает iteself * /

node * _kAltReverse(node *Node, int k, bool b) 

    if(Node == NULL) 

        return NULL; 

      

    int count = 1; 

    node *prev = NULL; 

    node *current = Node; 

    node *next; 

      

    / * Цикл служит двум целям

        1) Если b верно,

           тогда он переворачивает k узлов

        2) Если b ложно,

           затем он перемещает текущий указатель * /

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

    

        next = current->next; 

      

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

        if(b == true

            current->next = prev; 

                  

        prev = current; 

        current = next; 

        count++; 

    

          

    / * 3) Если b истинно, то узел является k-м узлом.

        Так что прикрепите остальную часть списка после узла.

        4) После прикрепления верните новую головку * /

    if(b == true

    

        Node->next = _kAltReverse(current, k, !b); 

        return prev;         

    

          

    / * Если b не верно, то присоединить

    Остальная часть списка после пред.

    Так что приложите остальную часть списка после пред * /

    else

    

        prev->next = _kAltReverse(current, k, !b); 

        return Node;     

    

  

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

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) 

    int count = 0; 

    while(node != NULL) 

    

        cout << node->data << " "

        node = node->next; 

        count++; 

    

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

int main(void

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

    node* head = NULL; 

    int i; 

  

    // создаем список 1-> 2-> 3-> 4-> 5 ...... -> 20

    for(i = 20; i > 0; i--) 

    push(&head, i); 

  

    cout << "Given linked list \n"

    printList(head); 

    head = kAltReverse(head, 3); 

  

    cout << "\nModified Linked list \n"

    printList(head); 

    return(0); 

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

С

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

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

struct node

{

    int data;

    struct node* next;

};

  
/ * Вспомогательная функция для kAltReverse () * /

struct node * _kAltReverse(struct node *node, int k, bool b);

  
/ * В качестве альтернативы обращает данный связанный список в группы

   заданный размер к. * /

struct node *kAltReverse(struct node *head, int k)

{

  return _kAltReverse(head, k, true);

}

   
/ * Вспомогательная функция для kAltReverse (). Он переворачивает k узлов списка, только если

    третий параметр b передается как true, в противном случае перемещается указатель k

    узлы впереди и рекурсивно вызывает iteself * / 

struct node * _kAltReverse(struct node *node, int k, bool b)

{

   if(node == NULL)

       return NULL;

  

   int count = 1;

   struct node *prev = NULL;

   struct node  *current = node;

   struct node *next;

   

   / * Цикл служит двум целям

      1) Если b истинно, то оно переворачивает k узлов

      2) Если b ложно, то он перемещает текущий указатель * /

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

   {

       next = current->next;

  

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

       if(b == true)

          current->next = prev;

              

       prev = current;

       current = next;

       count++;

   }

     

   / * 3) Если b истинно, то узел является k-м узлом.

       Так что прикрепите остальную часть списка после узла.

     4) После прикрепления верните новую головку * /

   if(b == true)

   {

        node->next = _kAltReverse(current,k,!b);

        return prev;        

   }

     

   / * Если b не соответствует истине, то прикрепить остаток списка после пред.

     Так что приложите остальную часть списка после пред * /    

   else

   {

        prev->next = _kAltReverse(current, k, !b);

        return node;       

   }

}

   

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

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)

{

    int count = 0;

    while(node != NULL)

    {

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

        node = node->next;

        count++;

    }

}

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

int main(void)

{

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

    struct node* head = NULL;

    int i;

   

    // создаем список 1-> 2-> 3-> 4-> 5 ...... -> 20

    for(i = 20; i > 0; i--)

      push(&head, i);

   

    printf("\n Given linked list \n");

    printList(head);

    head = kAltReverse(head, 3);

   

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

    printList(head);

   

    getchar();

    return(0);

}

Джава

// Java программа для обратного чередования k узлов в связанном списке

  

class LinkedList {

  

    static Node head;

  

    class Node {

  

        int data;

        Node next;

  

        Node(int d) {

            data = d;

            next = null;

        }

    }

  

    / * В качестве альтернативы обращает данный связанный список в группы

     заданный размер к. * /

    Node kAltReverse(Node head, int k) {

        return _kAltReverse(head, k, true);

    }

  

    / * Вспомогательная функция для kAltReverse (). Он переворачивает k узлов списка, только если

     третий параметр b передается как true, в противном случае перемещается указатель k

     узлы впереди и рекурсивно вызывает iteself * /

    Node _kAltReverse(Node node, int k, boolean b) {

        if (node == null) {

            return null;

        }

  

        int count = 1;

        Node prev = null;

        Node current = node;

        Node next = null;

  

        / * Цикл служит двум целям

         1) Если b истинно, то оно переворачивает k узлов

         2) Если b ложно, то он перемещает текущий указатель * /

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

            next = current.next;

  

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

            if (b == true) {

                current.next = prev;

            }

  

            prev = current;

            current = next;

            count++;

        }

  

        / * 3) Если b истинно, то узел является k-м узлом.

         Так что прикрепите остальную часть списка после узла.

         4) После прикрепления верните новую головку * /

        if (b == true) {

            node.next = _kAltReverse(current, k, !b);

            return prev;

        } / * Если b не соответствует истине, то прикрепить остаток списка после пред.

         Так что приложите остальную часть списка после пред * / else {

            prev.next = _kAltReverse(current, k, !b);

            return node;

        }

    }

  

    void printList(Node node) {

        while (node != null) {

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

            node = node.next;

        }

    }

  

    void push(int newdata) {

        Node mynode = new Node(newdata);

        mynode.next = head;

        head = mynode;

    }

  

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

  

        // Создание связанного списка

        for (int i = 20; i > 0; i--) {

            list.push(i);

        }

        System.out.println("Given Linked List :");

        list.printList(head);

        head = list.kAltReverse(head, 3);

        System.out.println("");

        System.out.println("Modified Linked List :");

        list.printList(head);

  

    }

}

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

C #

// C # Программа для конвертации
// односвязный список в
// круговой связанный список.

using System;

  

public class LinkedList

  

    static Node head; 

  

    public class Node 

    

  

        public int data; 

        public Node next; 

  

        public Node(int d) 

        

            data = d; 

            next = null

        

    

  

    / * Инвертирует альтернативные k узлов и

    возвращает указатель на новый головной узел * /

    Node kAltReverse(Node node, int k) 

    

        Node current = node; 

        Node next = null, prev = null

        int count = 0; 

  

        / * 1) поменять местами первые k узлов связного списка * /

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

        

            next = current.next; 

            current.next = prev; 

            prev = current; 

            current = next; 

            count++; 

        

  

        / * 2) Теперь голова указывает на k-й узел.

        Так что поменяйте следующую голову на (k + 1) -й узел * /

        if (node != null)

        

            node.next = current; 

        

  

        / * 3) Мы не хотим повернуть следующий

        k узлов. Так двигай ток

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

        count = 0; 

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

        

            current = current.next; 

            count++; 

        

  

        / * 4) Рекурсивно вызывать список

        начиная с текущего-> далее. И сделать

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

        if (current != null

        

            current.next = kAltReverse(current.next, k); 

        

  

        / * 5) предыдущая глава списка ввода * /

        return prev; 

    

  

    void printList(Node node) 

    

        while (node != null

        

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

            node = node.next; 

        

    

  

    void push(int newdata)

    

        Node mynode = new Node(newdata); 

        mynode.next = head; 

        head = mynode; 

    

  

    public static void Main(String[] args) 

    

        LinkedList list = new LinkedList(); 

  

        // Создание связанного списка

        for (int i = 20; i > 0; i--)

        

            list.push(i); 

        

        Console.WriteLine("Given Linked List :"); 

        list.printList(head); 

        head = list.kAltReverse(head, 3); 

        Console.WriteLine(""); 

        Console.WriteLine("Modified Linked List :"); 

        list.printList(head); 

    

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


Выход:

Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Modified Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

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

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

Обратные чередующиеся узлы K в односвязном списке

0.00 (0%) 0 votes