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

Question

Цель состоит в том, чтобы обратить целые числа 1 2 3 4 5 в 5 4 3 2 1.

Это определение структуры:

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;         // You should not change the definition of ListNode

typedef struct _linkedlist
{
    int size;
    ListNode *head;
} LinkedList;   

У меня есть функция, которая вызывается с использованием этого RecursiveReverse(&(ll.head));

void RecursiveReverse(ListNode **ptrHead)
{
    ListNode *curr,*q;
    curr = *ptrHead; //same as ll.head

    if(curr == NULL)
    {
        return;
    }

    if(curr->next == NULL)
    {
        *ptrHead = curr;
        return;
    }
    RecursiveReverse(&(curr->next));
    q = curr->next;
    q->next = curr;
    curr->next = NULL;
}

На этом этапе, если мой ввод 1 2 3, вывод только 1. Любая помощь приветствуется!

Answer 1

Поскольку у вас есть LinkedList в качестве структуры оболочки вокруг ListNode, вам нужно будет предоставить функцию-оболочку, которая принимает аргумент LinkedList* и затем вызывает реальную рекурсивную функцию, которая выполняет работу, передавая prev и current узлы в качестве аргументов. Это можно сделать следующим образом:

/** recursive reversal of list */
ListNode *revlist (ListNode *cur, ListNode *prev)
{
    if (cur->next != NULL) {
        ListNode *next = cur->next;
        cur->next = prev;
        return revlist (next, cur);
    }
    else {
        cur->next = prev;
        return cur;
    }
}

/** recursive reversal of list (wrapper) */
void rev (LinkedList *l)
{
    l->head = revlist (l->head, NULL);
}

В своем коде вы просто позвоните:

rev (ptr_to_list);

Примечание: с использованием обертки LinkedList хорошо также позволяет добавить указатель tail для вставок O (1) в конце.

Краткий пример, который строит и переворачивает список:

#include <stdio.h>
#include <stdlib.h>

typedef struct _listnode {
    int item;
    struct _listnode *next;
} ListNode;

typedef struct _linkedlist {
    int size;
    ListNode *head, *tail;
} LinkedList;

/** add node at end of list, update tail to end */
ListNode *add (LinkedList *l, int v)
{
    ListNode *node = malloc (sizeof *node); /* allocate node */
    if (!node) {                            /* validate allocation */
        perror ("malloc-node");
        return NULL;
    }
    node->item = v;                         /* initialize members values */
    node->next = NULL;

    if (!l->head)                   /* if 1st node, node is head/tail */
        l->head = l->tail = node;
    else {                          /* otherwise */
        l->tail->next = node;       /* add at end, update tail pointer */
        l->tail = node;
    }

    return node;    /* return new node */
}

/** print all nodes in list */
void prn (LinkedList *l)
{
    if (!l->head) {
        puts ("list-empty");
        return;
    }
    for (ListNode *n = l->head; n; n = n->next)
        printf (" %d", n->item);
    putchar ('\n');
}

/** delete all nodes in list */
void del (LinkedList *l)
{
    ListNode *n = l->head;
    while (n) {
        ListNode *victim = n;
        n = n->next;
        free (victim);
    }
}

/** recursive reversal of list */
ListNode *revlist (ListNode *cur, ListNode *prev)
{
    if (cur->next != NULL) {
        ListNode *next = cur->next;
        cur->next = prev;
        return revlist (next, cur);
    }
    else {
        cur->next = prev;
        return cur;
    }
}

/** recursive reversal of list (wrapper) */
void rev (LinkedList *l)
{
    l->head = revlist (l->head, NULL);
}

int main (void) {

    LinkedList l = { .size = 0 };

    for (int i = 0; i < 10; i++)
        add (&l, i+1);

    prn (&l);
    rev (&l);
    prn (&l);
    del (&l);
}

Пример Использование / Вывод

$ ./bin/lls_rec_rev
 1 2 3 4 5 6 7 8 9 10
 10 9 8 7 6 5 4 3 2 1

Использование памяти / проверка ошибок

В любом написанном вами коде, который динамически распределяет память, у вас есть 2 обязанностей относительно любого выделенного блока памяти: (1) всегда сохраняют указатель на начальный адрес для блока памяти, поэтому (2) он может быть освобожден , когда его нет требуется дольше.

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

Для Linux valgrind это нормальный выбор. Есть похожие проверки памяти для каждой платформы. Все они просты в использовании, просто запустите вашу программу через нее.

$ valgrind ./bin/lls_rec_rev
==7081== Memcheck, a memory error detector
==7081== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==7081== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==7081== Command: ./bin/lls_rec_rev
==7081==
 1 2 3 4 5 6 7 8 9 10
 10 9 8 7 6 5 4 3 2 1
==7081==
==7081== HEAP SUMMARY:
==7081==     in use at exit: 0 bytes in 0 blocks
==7081==   total heap usage: 11 allocs, 11 frees, 1,184 bytes allocated
==7081==
==7081== All heap blocks were freed -- no leaks are possible
==7081==
==7081== For counts of detected and suppressed errors, rerun with: -v
==7081== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

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

Answer 2

Этот код работает, попробуйте, я установил размер 5

#include <stdio.h>
#include <stdlib.h>

typedef struct _listnode
{
    int item;
    struct _listnode *next;
} ListNode;         // You should not change the definition of ListNode

struct _listnode* RecursiveReverse(struct _listnode* head)
{
    struct _listnode *temp = head;
    struct _listnode *curr = head;
    struct _listnode *prev = NULL;
    struct _listnode *next = NULL;
    int count = 0;

    // Reverses the first k nodes iteratively
    while (curr != NULL && count < 5){
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
            count++;
    }

    if (next != NULL) temp->next = RecursiveReverse(next);
    return prev;
}

int main() {
   struct _listnode* head = NULL; 
   struct _listnode* item2 = NULL; 
   struct _listnode* item3 = NULL; 
   struct _listnode* item4 = NULL; 
   struct _listnode* item5 = NULL; 

   struct _listnode* reverse = NULL; 

   head = (struct _listnode*)malloc(sizeof(struct _listnode));
   item2 = (struct _listnode*)malloc(sizeof(struct _listnode));
   item3 = (struct _listnode*)malloc(sizeof(struct _listnode));
   item4 = (struct _listnode*)malloc(sizeof(struct _listnode));
   item5 = (struct _listnode*)malloc(sizeof(struct _listnode));

   item5->item = 5;
   item5->next = NULL;

   item4->item = 4;
   item4->next = item5;

   item3->item = 3;
   item3->next = item4;

   item2->item = 2;
   item2->next = item3;

   head->item = 1;
   head->next = item2;

   reverse = RecursiveReverse(head);

   while (reverse != NULL) { 
      printf(" %d ", reverse->item); 
      reverse = reverse->next; 
   }

   return 0;
}