Рубрики

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

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

Примеры :

Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

Input: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULL

Input: NULL
Output: NULL

Input: 1->NULL
Output: 1->NULL

Итерационный метод

  1. Initialize three pointers prev as NULL, curr as head and next as NULL.
  2. Iterate trough the linked list. In loop, do following.
    // Before changing next of current,
    // store next node
    next = curr->next

    // Now change next of current
    // This is where actual reversing happens
    curr->next = prev

    // Move prev and curr one step forward
    prev = curr
    curr = next

Ниже приведена реализация вышеуказанного подхода:

C ++

// Итеративная программа на C ++ для обратного
// связанный список
#include <iostream>

using namespace std;

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

struct Node {

    int data;

    struct Node* next;

    Node(int data)

    {

        this->data = data;

        next = NULL;

    }

};

  

struct LinkedList {

    Node* head;

    LinkedList()

    {

        head = NULL;

    }

  

    / * Функция перевернуть связанный список * /

    void reverse()

    {

        // Инициализируем текущий, предыдущий и

        // следующие указатели

        Node* current = head;

        Node *prev = NULL, *next = NULL;

  

        while (current != NULL) {

            // Сохранить следующий

            next = current->next;

  

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

            current->next = prev;

  

            // Перемещаем указатели на одну позицию вперед.

            prev = current;

            current = next;

        }

        head = prev;

    }

  

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

    void print()

    {

        struct Node* temp = head;

        while (temp != NULL) {

            cout << temp->data << " ";

            temp = temp->next;

        }

    }

  

    void push(int data)

    {

        Node* temp = new Node(data);

        temp->next = head;

        head = temp;

    }

};

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

int main()

{

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

    LinkedList ll;

    ll.push(20);

    ll.push(4);

    ll.push(15);

    ll.push(85);

  

    cout << "Given linked list\n";

    ll.print();

  

    ll.reverse();

  

    cout << "\nReversed Linked list \n";

    ll.print();

    return 0;

}

С

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

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

struct Node {

    int data;

    struct Node* next;

};

  
/ * Функция перевернуть связанный список * /

static void reverse(struct Node** head_ref)

{

    struct Node* prev = NULL;

    struct Node* current = *head_ref;

    struct Node* next = NULL;

    while (current != NULL) {

        // Сохранить следующий

        next = current->next;

  

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

        current->next = prev;

  

        // Перемещаем указатели на одну позицию вперед.

        prev = current;

        current = next;

    }

    *head_ref = 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* head)

{

    struct Node* temp = head;

    while (temp != NULL) {

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

        temp = temp->next;

    }

}

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

int main()

{

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

    struct Node* head = NULL;

  

    push(&head, 20);

    push(&head, 4);

    push(&head, 15);

    push(&head, 85);

  

    printf("Given linked list\n");

    printList(head);

    reverse(&head);

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

    printList(head);

    getchar();

}

Джава

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

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    / * Функция перевернуть связанный список * /

    Node reverse(Node node)

    {

        Node prev = null;

        Node current = node;

        Node next = null;

        while (current != null) {

            next = current.next;

            current.next = prev;

            prev = current;

            current = next;

        }

        node = prev;

        return node;

    }

  

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

    void printList(Node node)

    {

        while (node != null) {

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

            node = node.next;

        }

    }

  

    public static void main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(85);

        list.head.next = new Node(15);

        list.head.next.next = new Node(4);

        list.head.next.next.next = new Node(20);

  

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

        list.printList(head);

        head = list.reverse(head);

        System.out.println("");

        System.out.println("Reversed linked list ");

        list.printList(head);

    }

}

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

питон

# Программа Python для обращения к связанному списку
# Сложность времени: O (n)
# Сложность пространства: O (1)

  
# Класс узла

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

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

    def __init__(self):

        self.head = None

  

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

    def reverse(self):

        prev = None

        current = self.head

        while(current is not None):

            next = current.next

            current.next = prev

            prev = current

            current = next

        self.head = prev

          

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

    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

  

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

llist = LinkedList()

llist.push(20)

llist.push(4)

llist.push(15)

llist.push(85)

  

print "Given Linked List"

llist.printList()
llist.reverse()

print "\nReversed Linked List"

llist.printList()

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

C #

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

using System;

  

class GFG {

    static void Main(string[] args)

    {

        LinkedList list = new LinkedList();

        list.AddNode(new LinkedList.Node(85));

        list.AddNode(new LinkedList.Node(15));

        list.AddNode(new LinkedList.Node(4));

        list.AddNode(new LinkedList.Node(20));

  

        // Список до обращения

        Console.WriteLine("Given linked list:");

        list.PrintList();

  

        // Перевернуть список

        list.ReverseList();

  

        // Список после обращения

        Console.WriteLine("Reversed linked list:");

        list.PrintList();

    }

}

  

class LinkedList {

    Node head;

  

    public class Node {

        public int data;

        public Node next;

  

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // функция для добавления нового узла в

    // конец списка

    public void AddNode(Node node)

    {

        if (head == null)

            head = node;

        else {

            Node temp = head;

            while (temp.next != null) {

                temp = temp.next;

            }

            temp.next = node;

        }

    }

  

    // функция для изменения списка

    public void ReverseList()

    {

        Node prev = null, current = head, next = null;

        while (current != null) {

            next = current.next;

            current.next = prev;

            prev = current;

            current = next;

        }

        head = prev;

    }

  

    // функция для печати данных списка

    public void PrintList()

    {

        Node current = head;

        while (current != null) {

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

            current = current.next;

        }

        Console.WriteLine();

    }

}

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



Выход:

Given linked list
85 15 4 20 
Reversed Linked list 
20 4 15 85 

Сложность времени: O (n)
Космическая сложность: O (1)

Рекурсивный метод:

   1) Divide the list in two parts - first node and 
      rest of the linked list.
   2) Call reverse for the rest of the linked list.
   3) Link rest to first.
   4) Fix head pointer

// Рекурсивная C ++ программа для реверса
// связанный список
#include <iostream>

using namespace std;

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

struct Node {

    int data;

    struct Node* next;

    Node(int data)

    {

        this->data = data;

        next = NULL;

    }

};

  

struct LinkedList {

    Node* head;

    LinkedList()

    {

        head = NULL;

    }

  

    Node* reverse(Node* head)

    {

        if (head == NULL || head->next == NULL)

            return head;

  

        / * перевернуть список отдыха и положить

          первый элемент в конце * /

        Node* rest = reverse(head->next);

        head->next->next = head;

  

        / * хитрый шаг - см. диаграмму * /

        head->next = NULL;

  

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

        return rest;

    }

  

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

    void print()

    {

        struct Node* temp = head;

        while (temp != NULL) {

            cout << temp->data << " ";

            temp = temp->next;

        }

    }

  

    void push(int data)

    {

        Node* temp = new Node(data);

        temp->next = head;

        head = temp;

    }

};

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

int main()

{

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

    LinkedList ll;

    ll.push(20);

    ll.push(4);

    ll.push(15);

    ll.push(85);

  

    cout << "Given linked list\n";

    ll.print();

  

    ll.head = ll.reverse(ll.head);

  

    cout << "\nReversed Linked list \n";

    ll.print();

    return 0;

}

Сложность времени: O (n)
Космическая сложность: O (1)

Более простой и рекурсивный метод
Ниже приведена реализация этого метода.

C ++

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

using namespace std;

  

struct Node {

    int data;

    struct Node* next;

};

  

void reverseUtil(Node* curr, Node* prev, Node** head);

  
// Эта функция в основном вызывает reverseUtil ()
// с prev как NULL

void reverse(Node** head)

{

    if (!head)

        return;

    reverseUtil(*head, NULL, head);

}

  
// Простая и хвостовая рекурсивная функция для обратного
// связанный список. prev передается как NULL изначально.

void reverseUtil(Node* curr, Node* prev, Node** head)

{

    / * Если последний узел пометил его головой * /

    if (!curr->next) {

        *head = curr;

  

        / * Обновление рядом с предыдущим узлом * /

        curr->next = prev;

        return;

    }

  

    / * Сохранить curr-> следующий узел для рекурсивного вызова * /

    Node* next = curr->next;

  

    / * и обновлять дальше .. * /

    curr->next = prev;

  

    reverseUtil(next, curr, head);

}

  
// Вспомогательная функция для создания нового узла

Node* newNode(int key)

{

    Node* temp = new Node;

    temp->data = key;

    temp->next = NULL;

    return temp;

}

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

void printlist(Node* head)

{

    while (head != NULL) {

        cout << head->data << " ";

        head = head->next;

    }

    cout << endl;

}

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

int main()

{

    Node* head1 = newNode(1);

    head1->next = newNode(2);

    head1->next->next = newNode(3);

    head1->next->next->next = newNode(4);

    head1->next->next->next->next = newNode(5);

    head1->next->next->next->next->next = newNode(6);

    head1->next->next->next->next->next->next = newNode(7);

    head1->next->next->next->next->next->next->next = newNode(8);

    cout << "Given linked list\n";

    printlist(head1);

    reverse(&head1);

    cout << "\nReversed linked list\n";

    printlist(head1);

    return 0;

}

Джава

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

  

class LinkedList {

  

    static Node head;

  

    static class Node {

  

        int data;

        Node next;

  

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Простая и хвостовая рекурсивная функция для обратного

    // связанный список. prev передается как NULL изначально.

    Node reverseUtil(Node curr, Node prev)

    {

  

        / * Если последний узел пометил его головой * /

        if (curr.next == null) {

            head = curr;

  

            / * Обновление рядом с предыдущим узлом * /

            curr.next = prev;

  

            return head;

        }

  

        / * Сохранить curr-> следующий узел для рекурсивного вызова * /

        Node next1 = curr.next;

  

        / * и обновлять дальше .. * /

        curr.next = prev;

  

        reverseUtil(next1, curr);

        return head;

    }

  

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

    void printList(Node node)

    {

        while (node != null) {

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

            node = node.next;

        }

    }

  

    public static void main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(1);

        list.head.next = new Node(2);

        list.head.next.next = new Node(3);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(5);

        list.head.next.next.next.next.next = new Node(6);

        list.head.next.next.next.next.next.next = new Node(7);

        list.head.next.next.next.next.next.next.next = new Node(8);

  

        System.out.println("Original Linked list ");

        list.printList(head);

        Node res = list.reverseUtil(head, null);

        System.out.println("");

        System.out.println("");

        System.out.println("Reversed linked list ");

        list.printList(res);

    }

}

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

питон

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

  
# Класс узла

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

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

    def __init__(self):

        self.head = None

  

  

    def reverseUtil(self, curr, prev):

          

        # Если последний узел пометил его головой

        if curr.next is None :

            self.head = curr 

              

            # Обновление рядом с предыдущим узлом

            curr.next = prev

            return 

          

        # Сохранить узел curr.next для рекурсивного вызова

        next = curr.next

  

        # И обновлять дальше

        curr.next = prev

      

        self.reverseUtil(next, curr) 

  

  

    # Эта функция в основном вызывает reverseUtil ()

    # с предыдущим как None

    def reverse(self):

        if self.head is None:

            return 

        self.reverseUtil(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

  

  
# Драйверная программа

llist = LinkedList()

llist.push(8)

llist.push(7)

llist.push(6)

llist.push(5)

llist.push(4)

llist.push(3)

llist.push(2)

llist.push(1)

  

print "Given linked list"

llist.printList()

  
llist.reverse()

  

print "\nReverse 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;

        }

    }

  

    // Простая и хвостовая рекурсивная функция для обратного

    // связанный список. prev передается как NULL изначально.

    Node reverseUtil(Node curr, Node prev)

    {

  

        / * Если последний узел пометил его головой * /

        if (curr.next == null) {

            head = curr;

  

            / * Обновление рядом с предыдущим узлом * /

            curr.next = prev;

  

            return head;

        }

  

        / * Сохранить curr-> следующий узел для рекурсивного вызова * /

        Node next1 = curr.next;

  

        / * и обновлять дальше .. * /

        curr.next = prev;

  

        reverseUtil(next1, curr);

        return head;

    }

  

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

    void printList(Node node)

    {

        while (node != null) {

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

            node = node.next;

        }

    }

  

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

    public static void Main(String[] args)

    {

        LinkedList list = new LinkedList();

        list.head = new Node(1);

        list.head.next = new Node(2);

        list.head.next.next = new Node(3);

        list.head.next.next.next = new Node(4);

        list.head.next.next.next.next = new Node(5);

        list.head.next.next.next.next.next = new Node(6);

        list.head.next.next.next.next.next.next = new Node(7);

        list.head.next.next.next.next.next.next.next = new Node(8);

  

        Console.WriteLine("Original Linked list ");

        list.printList(list.head);

        Node res = list.reverseUtil(list.head, null);

        Console.WriteLine("");

        Console.WriteLine("");

        Console.WriteLine("Reversed linked list ");

        list.printList(res);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Given linked list
1 2 3 4 5 6 7 8

Reversed linked list
8 7 6 5 4 3 2 1

Спасибо Gaurav Ahirwar за то, что он предложил это решение.

Рекурсивное обращение связанного списка (простая реализация)
Итеративно перевернуть связанный список, используя только 2 указателя (интересный метод)

Ссылки:
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

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

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

0.00 (0%) 0 votes