List chained in C - Reversing the nodes recursively

Question

List chained in C - Reversing the nodes recursively

Navigation

#1 by (1 votes)

0

I'm following Paulo Feofiloff's Algorithm Projects notes, and I'm with difficulties in resolving a question from the Chained Lists chapter, transcribed below:

Exercises 5

Write a function that reverses the order of cells in a linked list (the first one becomes the last, the second becomes the   penultimate, etc.). Do this without using auxiliary space, just by changing   pointers. Give two solutions: one iterative and one recursive.

I was able to come up with an iterative solution, but I could not even draw a recursive solution.

So I ask you to direct me to recursive solution to this problem. Thanks!

Follow the iterative solution code (please indicate improvements).

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

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

/*
Esta função recebe uma lista encadeada de inteiros e inverte a posição das
células desta lista usando apenas ponteiros. Ex.: o primeiro nó troca de lugar 
com o último, o segundo nó troca de lugar com o antepenúltimo, etc. 
*/

// versão iterativa
void swap_nodeI (NODE **head) {
    // if list is empty or there is only one node, nothing to do
    if (*head == NULL) return;

    // declare variables for first half of the list
    NODE *prevX = NULL, *currX = *head;
    int countX = 1;

    // declare variables for second half of the list
    NODE *prevY = NULL, *currY = *head; 
    int countY = 1;

    // count nodes (countY)
    for (; currY->next != NULL; currY = currY->next, ++countY);

    // swap nodes
    NODE *temp;
    int i, j;
    while (countX < countY) {

        // setup pointers
        for (currY = *head, i = 1; i != countY; ++i) {
            prevY = currY;
            currY = currY->next;
        }
        for (currX = *head, j = 1; j != countX; ++j) {
            prevX = currX;
            currX = currX->next;
        }

        // swap X and Y
        if (prevX != NULL) prevX->next = currY;
        else *head = currY;
        if (prevY != NULL) prevY->next = currX;
        else *head = currX;
        temp = currY->next;
        currY->next = currX->next;
        currX->next = temp;

        // update counters
        ++countX;
        --countY;
    }
}

c lista-encadeada

asked by anonymous 09.01.2018 / 01:11

1 answer

Insert ajax return into table How to use JSON in Python?

score 1 · Answer 1

After realizing that the strategy of inverting the list meets the statement, everything cleared up. I was determined to treat the equidistant pairs in the list, making the solution difficult. Even the iterative solution would be much simpler:

void reverse(NODE **head) {
    NODE *prev = NULL;
    NODE *curr = *head;
    NODE *next;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}

Follow recursive solution:

void reverseR(NODE **head) {

    /* Tratar lista vazia */
    if (*head == NULL) return;

    /* Atribuir um ponteiro para o nó atual
       e outro ponteiro para o restante da lista */
    NODE *curr;
    NODE *rest;
    curr = *head;
    rest = curr->next;

    /* Retornar ao chegar no final da lista */
    if (rest == NULL) return;

    /* Chamar a recursão até atingir o final da lista */
    reverseR(&rest);

    /* Inverter os nós e acertar a cabeça da lista */
    curr->next->next = curr;
    curr->next = NULL;
    *head = rest;
}