Comment revenir sur une seule liste liée à l’aide de seulement deux pointeurs ?

Question

Je me demandais si il existe une logique pour inverser la liste liée à l’aide de seulement deux pointeurs.

Ce qui suit est utilisé pour inverser la liste chaînée simple à l’aide de trois pointeurs à savoir p, q, r :

Y a-t-il n’importe quel autre suppléant pour inverser la liste chaînée ? quelle serait la meilleure logique pour inverser une seule liste liée, en termes de complexité en temps ?

Answer 1

Je déteste être le porteur de mauvaises nouvelles, mais je ne pense pas que vos trois pointeur de la solution fonctionne réellement. Lorsque je l'ai utilisé dans le test suivant harnais, la liste a été réduite à un nœud, comme par la sortie suivante:

==========
4
3
2
1
0
==========
4
==========

Vous n'obtiendrez pas de meilleur moment de la complexité de votre solution, car il est O(n) et vous avez à visiter chaque nœud afin de modifier les pointeurs, mais vous pouvez faire une solution avec seulement deux pointeurs assez facilement, comme illustré dans le code suivant:

#include <stdio.h>

// The list element type and head.

struct node { 
    int data;
    struct node *link;
};
static struct node *first = NULL;

// A reverse function which uses only two extra pointers.

void reverse() {
    // curNode traverses the list, first is reset to empty list.
    struct node *curNode = first, *nxtNode;
    first = NULL;

    // Until no more in list, insert current before first and advance.
    while (curNode != NULL) {
        // Need to save next node since we're changing the current.
        nxtNode = curNode->link;

        // Insert at start of new list.
        curNode->link = first;
        first = curNode;

        // Advance to next.
        curNode = nxtNode;
    }
}

// Code to dump the current list.

static void dumpNodes() {
    struct node *curNode = first;
    printf ("==========\n");
    while (curNode != NULL) {
        printf ("%d\n", curNode->data);
        curNode = curNode->link;
    }
}

// Test harness main program.

int main (void) {
    int i;
    struct node *newnode;

    // Create list (using actually the same insert-before-first
    // that is used in reverse function.

    for (i = 0; i < 5; i++) {
        newnode = malloc (sizeof (struct node));
        newnode->data = i;
        newnode->link = first;
        first = newnode;
    }

    // Dump list, reverse it, then dump again.

    dumpNodes();
    reverse();
    dumpNodes();
    printf ("==========\n");

    return 0;
}

Ce code affiche:

==========
4
3
2
1
0
==========
0
1
2
3
4
==========

je pense que c'est ce que vous avez été au bout. Il est possible de faire ça depuis que, une fois que vous avez chargé first dans le pointeur de la traversée de la liste, vous pouvez ré-utiliser first .

Answer 2

#include <stddef.h>

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

Node * reverse(Node *cur) {
    Node *prev = NULL;
    while (cur) {
        Node *temp = cur;
        cur = cur->next; // advance cur
        temp->next = prev;
        prev = temp; // advance prev
    }
    return prev;
}

Answer 3

Voici le code pour inverser une seule liste liée dans C.

Et ici il est collé ci-dessous :

Answer 4

Oui. Je suis sûr que vous pouvez le faire de la même façon , vous pouvez échanger les deux nombres sans l'aide d'un tiers. Tout simplement jeté les pointeurs vers un int/long et effectuer l'opération XOR une couple de fois. C'est l'un de ces C des trucs qui en fait un plaisir question, mais n'ont pas de valeur pratique.

Pouvez-vous réduire le O(n) la complexité? Non, pas vraiment. Il suffit d'utiliser une liste doublement chaînée si vous pensez que vous allez avoir besoin l'ordre inverse.