Рубрики

Переместить последний элемент в начало данного связанного списка

Напишите функцию, которая перемещает последний элемент вперед в заданный список с однократной связью. Например, если данный связанный список 1-> 2-> 3-> 4-> 5, то функция должна изменить список на 5-> 1-> 2-> 3-> 4.

Алгоритм:
Пройдите по списку до последнего узла. Используйте два указателя: один для хранения адреса последнего узла и другой для адреса второго последнего узла. После окончания цикла выполните следующие операции.
я) Сделать второй последний как последний (secLast-> next = NULL).
ii) Установить следующий из последних как head (last-> next = * head_ref).
iii) Сделать последним в качестве головы (* head_ref = last)

C ++

/ * Программа CPP для перемещения последнего элемента
вперед в заданном связанном списке * /
#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node *next; 

}; 

  
/ * Мы используем двойной указатель
head_ref здесь, потому что мы меняем
глава связанного списка внутри
эта функция. * /

void moveToFront(Node **head_ref) 

    / * Если связанный список пуст, или

    он содержит только один узел,

    тогда ничего не нужно делать,

    просто верните *

    if (*head_ref == NULL || (*head_ref)->next == NULL) 

        return

  

    / * Инициализировать второй последний

    и последние указатели * /

    Node *secLast = NULL; 

    Node *last = *head_ref; 

  

    / * После этого цикла secLast содержит

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

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

    while (last->next != NULL) 

    

        secLast = last; 

        last = last->next; 

    

  

    / * Установить следующую секунду последней в качестве NULL * /

    secLast->next = NULL; 

  

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

    last->next = *head_ref; 

  

    / * Изменить указатель головы

    указать на последний узел сейчас * /

    *head_ref = last; 

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

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

    Node *start = NULL; 

  

    / * Составленный связанный список:

    1-> 2-> 3-> 4-> 5 * /

    push(&start, 5); 

    push(&start, 4); 

    push(&start, 3); 

    push(&start, 2); 

    push(&start, 1); 

  

    cout<<"Linked list before moving last to front\n"

    printList(start); 

  

    moveToFront(&start); 

  

    cout<<"\nLinked list after removing last to front\n"

    printList(start); 

  

    return 0; 

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

С

/ * C Программа для перемещения последнего элемента вперед в заданном связанном списке * /
#include<stdio.h>
#include<stdlib.h>

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

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Мы используем двойной указатель head_ref здесь, потому что мы меняем

   Глава связанного списка внутри этой функции. * /

void moveToFront(struct Node **head_ref)

{

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

      тогда ничего не нужно делать, просто вернуть * /

    if (*head_ref == NULL || (*head_ref)->next == NULL)

        return;

  

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

    struct Node *secLast = NULL;

    struct Node *last = *head_ref;

  

    / * После этого цикла secLast содержит адрес второго последнего

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

    while (last->next != NULL)

    {

        secLast = last;

        last = last->next;

    }

  

    / * Установить следующую секунду последней в качестве NULL * /

    secLast->next = NULL;

  

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

    last->next = *head_ref;

  

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

    *head_ref = last;

}

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

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

{

    struct Node *start = NULL;

  

    / * Составленный связанный список:

     1-> 2-> 3-> 4-> 5 * /

    push(&start, 5);

    push(&start, 4);

    push(&start, 3);

    push(&start, 2);

    push(&start, 1);

  

    printf("\n Linked list before moving last to front\n");

    printList(start);

  

    moveToFront(&start);

  

    printf("\n Linked list after removing last to front\n");

    printList(start);

  

    return 0;

}

Джава

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

class LinkedList

{

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

   

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

    class Node

    {

        int data;

        Node next;

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

    }

  

    void moveToFront()

    {

        / * Если связанный список пуст или содержит только

           затем один узел просто возвращается. * /

           if(head == null || head.next == null

              return;

  

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

        Node secLast = null;

        Node last = head;

  

        / * После этого цикла secLast содержит адрес

           второй последний узел и последний содержит адрес

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

        while (last.next != null)  

        {

           secLast = last;

           last = last.next; 

        }

  

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

        secLast.next = null;

  

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

        last.next = head;

  

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

        head = last;

    }                 

  

                      

    / * Сервисные функции * /

  

    / * Вставляет новый узел в начало списка. * /

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

        / * Построенный связанный список 1-> 2-> 3-> 4-> 5-> null * /

        llist.push(5);

        llist.push(4);

        llist.push(3);

        llist.push(2);

        llist.push(1);

          

        System.out.println("Linked List before moving last to front ");

        llist.printList();

          

        llist.moveToFront();

          

        System.out.println("Linked List after moving last to front ");

        llist.printList();

    }

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

python3

# Python3 код для перемещения последнего элемента вперед

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

    def __init__(self):

        self.head = None

  

    # Функция для добавления узла

    # в начале связанного списка

    def push(self, data):

        new_node = Node(data)

        new_node.next = self.head

        self.head = new_node

          

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

    # данный связанный список

    def printList(self):

        tmp = self.head

        while tmp is not None:

            print(tmp.data, end=", ")

            tmp = tmp.next

        print()

  

    # Функция для вывода последнего узла на передний план

    def moveToFront(self):

        tmp = self.head

        sec_last = None # Чтобы отслеживать

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

  

    # Проверить, не получили ли мы

    # пустой список или список с одним узлом

        if not tmp or not tmp.next

            return

  

        # Итерировать до конца, чтобы получить

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

        while tmp and tmp.next :

            sec_last = tmp

            tmp = tmp.next

  

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

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

        sec_last.next = None

  

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

        tmp.next = self.head

        self.head = tmp

  
Код водителя

if __name__ == '__main__':

    llist = LinkedList()

      

    # поменяйте местами 2 узла

    llist.push(5)

    llist.push(4)

    llist.push(3)

    llist.push(2)

    llist.push(1)

    print ("Linked List before moving last to front ")

    llist.printList()

    llist.moveToFront()

    print ("Linked List after moving last to front ")

    llist.printList()

C #

/ * C # Программа для перемещения последнего элемента вперед в заданном связанном списке * /

using System;

class LinkedList 

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

  

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

    public class Node 

    

        public int data; 

        public Node next; 

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

    

  

    void moveToFront() 

    

        / * Если связанный список пуст или содержит только

        затем один узел просто возвращается. * /

        if(head == null || head.next == null

            return

  

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

        Node secLast = null

        Node last = head; 

  

        / * После этого цикла secLast содержит адрес

        второй последний узел и последний содержит адрес

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

        while (last.next != null

        

        secLast = last; 

        last = last.next; 

        

  

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

        secLast.next = null

  

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

        last.next = head; 

  

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

        head = last; 

    }                 

  

                      

    / * Сервисные функции * /

  

    / * Вставляет новый узел в начало списка. * /

    public 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(String []args) 

    

        LinkedList llist = new LinkedList(); 

        / * Построенный связанный список 1-> 2-> 3-> 4-> 5-> null * /

        llist.push(5); 

        llist.push(4); 

        llist.push(3); 

        llist.push(2); 

        llist.push(1); 

          

        Console.WriteLine("Linked List before moving last to front "); 

        llist.printList(); 

          

        llist.moveToFront(); 

          

        Console.WriteLine("Linked List after moving last to front "); 

        llist.printList(); 

    


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


Выход:

 Linked list before moving last to front 
1 2 3 4 5 
 Linked list after removing last to front 
5 1 2 3 4

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

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

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

Переместить последний элемент в начало данного связанного списка

0.00 (0%) 0 votes