Рубрики

Поменять K-й узел с начала на K-й узел с конца в связанном списке

Если задан односвязный список, поменяйте местами k-й узел с начала с k-го узла с конца. Обмен данными не допускается, только указатели должны быть изменены. Это требование может быть логичным во многих ситуациях, когда часть данных связанного списка огромна (например, строка с подробной информацией об ученике, RollNo, Address, ..etc). Указатели всегда фиксированы (4 байта для большинства компиляторов).

На первый взгляд проблема кажется простой, но у нее много интересных случаев.

Пусть X будет k-м узлом от начала, а Y будет k-м узлом с конца. Ниже приведены интересные случаи, которые должны быть обработаны.
1) Y рядом с X
2) Х рядом с Y
3) X и Y одинаковы
4) X и Y не существуют (k больше, чем количество узлов в связанном списке)

C ++

// Программа на C ++ для замены K-го узла с начала на k-й узел с конца
#include <iostream>
#include <stdlib.h>

using namespace std;

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

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Утилита для вставки узла в начале * /

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)

    {

        cout << node->data << " ";

        node = node->next;

    }

    cout << endl;

}

  
/ * Утилита для расчета длины связанного списка * /

int countNodes(struct Node *s)

{

    int count = 0;

    while (s != NULL)

    {

        count++;

        s = s->next;

    }

    return count;

}

  
/ * Функция для замены k-х узлов с обоих концов связанного списка * /

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

{

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

    int n = countNodes(*head_ref);

  

    // Проверить, действительно ли k

    if (n < k)  return;

  

    // Если x (k-й узел от начала) и y (k-й узел от конца) одинаковы

    if (2*k - 1 == n) return;

  

    // Найти k-ый узел от начала связанного списка. Мы также находим

    // предыдущий k-го узла, потому что нам нужно обновить следующий указатель

    // предыдущий.

    Node *x = *head_ref;

    Node *x_prev = NULL;

    for (int i = 1; i < k; i++)

    {

        x_prev = x;

        x = x->next;

    }

  

    // Аналогично, найти k-й узел из конца и его предыдущего. K-й узел

    // с конца есть (n-k + 1) -й узел с начала

    Node *y = *head_ref;

    Node *y_prev = NULL;

    for (int i = 1; i < n-k+1; i++)

    {

        y_prev = y;

        y = y->next;

    }

  

    // Если x_prev существует, то новым следующим будет y. Рассмотрим случай

    // когда y-> next равно x, в этом случае x_prev и y совпадают. Итак, утверждение

    // "x_prev-> next = y" создает цикл self. Эта самостоятельная петля будет разорвана

    // когда мы меняем y-> next.

    if (x_prev)

        x_prev->next = y;

  

    // То же самое относится к y_prev

    if (y_prev)

        y_prev->next = x;

  

    // Меняем местами следующие указатели на x и y. Эти заявления также ломают себя

    // цикл, если x-> next равно y или y-> next равно x

    Node *temp = x->next;

    x->next = y->next;

    y->next = temp;

  

    // Изменить указатели головы, когда k равно 1 или n

    if (k == 1)

        *head_ref = y;

    if (k == n)

        *head_ref = x;

}

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

int main()

{

    // Давайте создадим следующий связанный список для тестирования

    // 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8

    struct Node *head = NULL;

    for (int i = 8; i >= 1; i--)

       push(&head, i);

  

    cout << "Original Linked List: ";

    printList(head);

  

    for (int k = 1; k < 9; k++)

    {

        swapKth(&head, k);

        cout << "\nModified List for k = " << k << endl;

        printList(head);

    }

  

    return 0;

}

Джава

// Java-программа для замены k-го узла с начала
// k-й узел с конца

  

class Node

{

    int data;

    Node next;

    Node(int d) { data = d;  next = null; }

}

  

class LinkedList

{

    Node head;

  

    / * Утилита для вставки узла в начале * /

    void push(int new_data)

    {

        Node new_node = new Node(new_data);

        new_node.next = head;

        head = new_node;

    }

  

    / * Утилита для отображения связанного списка * /

    void printList()

    {

        Node node = head;

        while (node != null)

        {

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

            node = node.next;

        }

        System.out.println("");

    }

  

    / * Утилита для расчета длины связанного списка * /

    int countNodes()

    {

        int count = 0;

        Node s = head;

        while (s != null)

        {

            count++;

            s = s.next;

        }

        return count;

    }

  

    / * Функция для замены k-х узлов с обоих концов

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

    void swapKth(int k)

    {

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

        int n = countNodes();

  

        // Проверить, действительно ли k

        if (n < k)

            return;

  

        // Если x (k-й узел от начала) и y (k-й узел от конца)

        // одинаковы

        if (2*k - 1 == n)

            return;

  

        // Найти k-ый узел от начала связанного списка.

        // Мы также находим предыдущий k-й узел, потому что нам нужно

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

        Node x = head;

        Node x_prev = null;

        for (int i = 1; i < k; i++)

        {

            x_prev = x;

            x = x.next;

        }

  

        // Точно так же, найти k-й узел от конца и его

        // предыдущий k-й узел от конца - это (n-k + 1) -й узел

        // с начала

        Node y = head;

        Node y_prev = null;

        for (int i = 1; i < n - k + 1; i++)

        {

            y_prev = y;

            y = y.next;

        }

  

        // Если x_prev существует, то новым следующим будет y.

        // Рассмотрим случай, когда y-> next равно x, в этом случае

        // x_prev и y одинаковы. Итак, утверждение

        // "x_prev-> next = y" создает цикл self. Это я

        // цикл будет прерван, когда мы изменим y-> next.

        if (x_prev != null)

            x_prev.next = y;

  

        // То же самое относится к y_prev

        if (y_prev != null)

            y_prev.next = x;

  

        // Меняем местами следующие указатели на x и y. Эти заявления

        // также прерывать цикл себя, если x-> next равно y или y-> next

        // это х

        Node temp = x.next;

        x.next = y.next;

        y.next = temp;

  

        // Изменить указатели головы, когда k равно 1 или n

        if (k == 1)

            head = y;

  

        if (k == n)

            head = x;

    }

  

    // Код драйвера для проверки выше

    public static void main(String[] args)

    {

        LinkedList llist = new LinkedList();

        for (int i = 8; i >= 1; i--)

            llist.push(i);

  

        System.out.print("Original linked list: ");

        llist.printList();

        System.out.println("");

  

        for (int i = 1; i < 9; i++)

        {

            llist.swapKth(i);

            System.out.println("Modified List for k = " + i);

            llist.printList();

            System.out.println("");

        }

    }

}

python3

«»»
Программа Python3 для замены k-го узла с
начало с k-го узла от конца
«»»

class Node:

    def __init__(self, data, next = None):

        self.data = data

        self.next = next

      

class LinkedList:

  

    def __init__(self, *args, **kwargs):

        self.head = Node(None)

    «»»

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

    @args:

        данные: значение узла

    «»»

    def push(self, data):

        node = Node(data)

        node.next = self.head

        self.head = node

      

    # Распечатать связанный список

    def printList(self):

        node = self.head

        while node.next is not None:

            print(node.data, end = " ")

            node = node.next

      

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

    def countNodes(self):

        count = 0

        node = self.head

        while node.next is not None:

            count += 1

            node = node.next

        return count

      

    «»»

    Функция для обмена K-ными узлами с

    оба конца связанного списка

    «»»

    def swapKth(self, k):

  

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

        n = self.countNodes()

  

        # проверить, действительно ли k

        if n<k:

            return

  

        «»»

        Если x (k-й узел от начала) и

        у (k-й узел от конца) одинаковы

        «»»

        if (2 * k - 1) == n:

            return

  

        «»»

        Найти k-й узел в начале связанного списка.

        Мы также находим предыдущий из k-го узла, потому что нам нужно

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

        «»»

        x = self.head

        x_prev = Node(None)

        for i in range(k - 1):

            x_prev = x

            x = x.next

  

        «»»

        Точно так же найдите k-й узел от конца и его

        предыдущая. k-й узел от конца - это (n-k + 1) -й узел

        с начала

        «»»

        y = self.head

        y_prev = Node(None)

        for i in range(n - k):

            y_prev = y

            y = y.next

  

        «»»

        Если x_prev существует, то новым следующим будет y.

        Рассмотрим случай, когда y-> next равно x, в этом случае

        x_prev и y одинаковы. Итак, утверждение

        "x_prev-> next = y" создает цикл self. Это я

        цикл будет прерван, когда мы изменим y-> next.

        «»»

        if x_prev is not None:

            x_prev.next = y

  

        # То же самое относится и к y_prev

        if y_prev is not None:

            y_prev.next = x

          

        «»»

        Поменяйте местами следующие указатели x и y. Эти заявления

        также прервать цикл self, если x-> next равно y или y-> next

        это х

        «»»

        temp = x.next

        x.next = y.next

        y.next = temp

  

        # Изменить указатели головы, когда k равен 1 или n

        if k == 1:

            self.head = y

          

        if k == n:

            self.head = x

  
Код водителя

llist = LinkedList()

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

    llist.push(i)

llist.printList()

  

  

for i in range(1, 9):

    llist.swapKth(i)

    print("Modified List for k = ", i)

    llist.printList()

    print("\n")

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

C #

// C # программа для замены k-го узла с начала
// k-й узел с конца

using System;

  

public class Node 

    public int data; 

    public Node next; 

    public Node(int d) { data = d; next = null; } 

  

public class LinkedList 

    Node head; 

  

    / * Утилита для вставки

    узел в начале * /

    void push(int new_data) 

    

        Node new_node = new Node(new_data); 

        new_node.next = head; 

        head = new_node; 

    

  

    / * Утилита для отображения связанного списка * /

    void printList() 

    

        Node node = head; 

        while (node != null

        

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

            node = node.next; 

        

        Console.WriteLine(""); 

    

  

    / * Полезная функция для расчета

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

    int countNodes() 

    

        int count = 0; 

        Node s = head; 

        while (s != null

        

            count++; 

            s = s.next; 

        

        return count; 

    

  

    / * Функция для обмена K-ными узлами с

    оба конца связанного списка * /

    void swapKth(int k) 

    

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

        int n = countNodes(); 

  

        // Проверить, действительно ли k

        if (n < k) 

            return

  

        // Если x (k-й узел от начала) и y (k-й узел от конца)

        // одинаковы

        if (2*k - 1 == n) 

            return

  

        // Найти k-ый узел от начала связанного списка.

        // Мы также находим предыдущий k-й узел, потому что нам нужно

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

        Node x = head; 

        Node x_prev = null

        for (int i = 1; i < k; i++) 

        

            x_prev = x; 

            x = x.next; 

        

  

        // Точно так же, найти k-й узел от конца и его

        // предыдущий k-й узел от конца - это (n-k + 1) -й узел

        // с начала

        Node y = head; 

        Node y_prev = null

        for (int i = 1; i < n - k + 1; i++) 

        

            y_prev = y; 

            y = y.next; 

        

  

        // Если x_prev существует, то новым следующим будет y.

        // Рассмотрим случай, когда y-> next равно x, в этом случае

        // x_prev и y одинаковы. Итак, утверждение

        // "x_prev-> next = y" создает цикл self. Это я

        // цикл будет прерван, когда мы изменим y-> next.

        if (x_prev != null

            x_prev.next = y; 

  

        // То же самое относится к y_prev

        if (y_prev != null

            y_prev.next = x; 

  

        // Меняем местами следующие указатели на x и y. Эти заявления

        // также прерывать цикл себя, если x-> next равно y или y-> next

        // это х

        Node temp = x.next; 

        x.next = y.next; 

        y.next = temp; 

  

        // Изменить указатели головы, когда k равно 1 или n

        if (k == 1) 

            head = y; 

  

        if (k == n) 

            head = x; 

    

  

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

    public static void Main(String[] args) 

    

        LinkedList llist = new LinkedList(); 

        for (int i = 8; i >= 1; i--) 

            llist.push(i); 

  

        Console.Write("Original linked list: "); 

        llist.printList(); 

        Console.WriteLine(""); 

  

        for (int i = 1; i < 9; i++) 

        

            llist.swapKth(i); 

            Console.WriteLine("Modified List for k = " + i); 

            llist.printList(); 

            Console.WriteLine(""); 

        

    

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

[/исходный код]


Выход:

Original Linked List: 1 2 3 4 5 6 7 8

Modified List for k = 1
8 2 3 4 5 6 7 1

Modified List for k = 2
8 7 3 4 5 6 2 1

Modified List for k = 3
8 7 6 4 5 3 2 1

Modified List for k = 4
8 7 6 5 4 3 2 1

Modified List for k = 5
8 7 6 4 5 3 2 1

Modified List for k = 6
8 7 3 4 5 6 2 1

Modified List for k = 7
8 2 3 4 5 6 7 1

Modified List for k = 8
1 2 3 4 5 6 7 8

Обратите внимание, что приведенный выше код запускает три отдельных цикла для подсчета узлов, поиска x и x prev и поиска y и y_prev. Эти три вещи могут быть выполнены в одном цикле. Код использует три цикла, чтобы сделать вещи простыми и читаемыми.

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

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

Поменять K-й узел с начала на K-й узел с конца в связанном списке

0.00 (0%) 0 votes