Сторнирование связанного списка, начиная с хвоста, используя рекурсию - PullRequest
Новая
       41

Сторнирование связанного списка, начиная с хвоста, используя рекурсию

0 голосов
/ 22 мая 2018

Я все еще борюсь с техникой рекурсии, чтобы решить проблему.Я знаю, что есть более хорошие способы решить мою проблему ниже - перевернуть связанный список.Большинство способов, которые я видел, начинают изменять указатели, переходя от головы к хвосту, используя итерацию или рекурсию.

Я пытаюсь для интереса отменить список, сначала найдя последнийузел в списке рекурсивно, а затем меняйте указатели каждый раз, когда функция возвращает.

Что я делаю неправильно ниже точно?Или этот метод будет работать без необходимости передавать больше параметров в рекурсивную функцию?Заранее благодарим за помощь. 

struct Node
{
    int data;
    struct Node *next;
};

Node* Reverse(Node *head)
{
    static Node* firstNode = head;
    // if no list return head
    if (head == NULL)
    {
        return head;
    }

    Node* prev = NULL;
    Node* cur = head;

    // reached last node in the list, return head
    if (cur->next == NULL)
    {
        head = cur;
        return head;
    }

    prev = cur;
    cur = cur->next;
    Reverse(cur)->next = prev;

    if (cur == firstNode)
    {
        cur->next = NULL;
        return head;
    }
    return cur;
}

РЕДАКТИРОВАТЬ: еще одна попытка 

Node* ReverseFromTail(Node* prev, Node* cur, Node** head);

Node* ReverseInit(Node** head)
{
    Node* newHead = ReverseFromTail(*head, *head, head);
    return newHead;
}



Node* ReverseFromTail(Node* prev, Node* cur, Node** head)
{
    static int counter = 0;
    counter++;

    // If not a valid list, return head
    if (head == NULL)
    {
        return *head;
    }

    // Reached end of list, start reversing pointers
    if (cur->next == NULL)
    {
        *head = cur;
        return cur;
    }


    Node* retNode = ReverseFromTail(cur, cur->next, head);
    retNode->next = cur;


    // Just to force termination of recursion when it should. Not a permanent solution 
    if (counter == 3)
    {
        cur->next = NULL;
        return *head;
    }

    return retNode;
}

Наконец решено это: 

Node* NewestReverseInit(Node* head)
{
    // Invalid List, return
    if (!head)
    {
        return head;
    }

    Node* headNode = NewestReverse(head, head, &head);

    return headNode;
}

Node* NewestReverse(Node *cur, Node* prev, Node** head)
{
    // reached last node in the list, set new head and return
    if (cur->next == NULL)
    {
        *head = cur;
        return cur;
    }

    NewestReverse(cur->next, cur, head)->next = cur;

    // Returned to the first node where cur = prev from initial call
    if (cur == prev)
    {
        cur->next = NULL;
        return *head;
    }

    return cur;
}

Ответы [ 3 ]

0 голосов
/ 22 мая 2018

Я не дам вам код, я дам вам идею.Вы можете реализовать идею в коде.

Ключом ко всем проблемам рекурсии является выяснение двух случаев: шаг повторения и конец случая.Как только вы это сделаете, он работает почти как по волшебству.

Применение этого принципа к обращению связанного списка:

  • Конечный случай: список одного элемента уже перевернут (этопросто) и возвращая сам элемент
  • Случай повторения: для заданного списка L обращение этого наименьшего значения означает обращение L ', где L' - это L '- список без самого первого элемента (обычно называемого head), а затем добавить голову в качестве последнего элемента списка.Возвращаемое значение будет таким же, как возвращаемое значение только что сделанного вами рекурсивного вызова.
0 голосов
/ 22 мая 2018

Это можно сделать.Ключом к пониманию рекурсии является Какая отправная точка?

Обычно я создаю «стартовую» функцию, которая готовит первый вызов.Иногда это отдельная функция (как в неосуществленной реализации внизу).Иногда это просто специальный первый вызов (как в примере ниже).

Кроме того, ключ в том, чтобы запоминать переменные до их изменения и что такое new head.

Новый head является последним элементом списка.Таким образом, Вы должны поднять это из нижней части списка.

Элемент next всегда является вашим родителем.

Тогда уловка состоит в том, чтобы сделать все в правильном порядке. 

    Node* Reverse( Node* parent) // Member function of Node.
    {
        Node* new_head = next ? next->Reverse( this ) 
                              : this;

        next = parent;

        return new_head;
    }

Вы вызываете функцию с помощью: var.Reverse( nullptr);

Пример: 

int main()
{
    Node d{ 4, nullptr };
    Node c{ 3, &d };
    Node b{ 2, &c };
    Node a{ 1, &b };

    Node* reversed = a.Reverse( nullptr );
}

Так что здесь происходит?

Сначала мы создаем связанныйlist: 

 a->b->c->d->nullptr

Затем вызывается функция:

  1. a.Reverse(nullptr).
  2. Это вызывает Reverse на следующем узле b.Reverseс родителем a.
  3. Это вызывает Reverse на следующем узле c.Reverse с родителем b.
  4. Это вызывает Reverse на следующем узле d.Reverseс родителем c.
  5. d не имеет узла next, поэтому он говорит, что новая голова сама по себе.
  6. d s next теперь этоparent c
  7. d возвращает себя как new_head.
  8. Назад к c: new_head, возвращаемое из d равно d
  9. c next теперь является его родителем b
  10. c возвращает new_headполучено от d
  11. Назад к b: new_head возвращено от c is d
  12. b s next теперь является его родителем a
  13. b возвращает new_head, полученное от c
  14. Назад к a: new_head, возвращаемое с b, равно d
  15. a next теперь является его родителем nullptr
  16. a возвращает new_head, полученное от b
  17. d, возвращается

Не объектно-ориентированная реализация; 

Node* reverse_impl(Node* parent)
{
    Node* curr = parent->next;
    Node* next = curr->next;

    Node* new_head = next ? reverse_impl( curr ) 
                          : curr;

    curr->next = parent;

    return new_head;
}

Node* reverse(Node* start)
{
    if ( !start )
        return nullptr;

    Node* new_head = reverse_impl( start );
    start->next    = nullptr;

    return new_head;
}
0 голосов
/ 22 мая 2018

Вот полная реализация, которую я написал за 5 минут: 

#include <stdio.h>

struct Node
{
     int data;
     struct Node *next;
};

struct Node* Reverse(struct Node *n)
{
    static struct Node *first = NULL;

    if(first == NULL)
      first = n;

    // reached last node in the list
    if (n->next == NULL)
      return n;

    Reverse(n->next)->next = n;

    if(n == first)
    {
      n->next = NULL;
      first = NULL;     
    }

    return n;
}

void linked_list_walk(struct Node* n)
{
  printf("%d", n->data);
  if(n->next)
    linked_list_walk(n->next);
  else
    printf("\n");
}

int main()
{
  struct Node n[10];
  int i;

  for(i=0;i<10;i++)
  {
    n[i].data = i;
    n[i].next = n + i + 1;
  }
  n[9].next = NULL;

  linked_list_walk(n);
  Reverse(n);
  linked_list_walk(n+9);
}

Вывод: 

0123456789                                                                                                                                                                          
9876543210
...