Рубрики

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

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

Примеры:

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

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

С

#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;

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

}


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

void recursiveReverse(struct Node** head_ref)

{

    struct Node* first;

    struct Node* rest;

       

    / * пустой список * /

    if (*head_ref == NULL)

       return;   

  

    / * предположим, что first = {1, 2, 3}, rest = {2, 3} * /

    first = *head_ref;  

    rest  = first->next;

  

    / * Список имеет только один узел * /

    if (rest == NULL)

       return;   

  

    / * инвертировать список остальных и поместить первый элемент в конец * /

    recursiveReverse(&rest);

    first->next->next  = first;  

      

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

    first->next  = NULL;          

  

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

    *head_ref = rest;              

}

Более простой и рекурсивный метод

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;

}


Пожалуйста, обратитесь к полной статье на Обратный связанный список для более подробной информации!

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

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

0.00 (0%) 0 votes