Wie kehrt man eine einfach verknüpfte Liste mit nur zwei Zeigern um?

Ich frage mich, ob es eine Logik gibt, um eine einfach verknüpfte Liste mit nur zwei Zeigern umzukehren.

Das Folgende wird nämlich verwendet, um die einzelne verkettete Liste unter Verwendung von drei Zeigern umzukehren p, q, r:

struct node {
    int data;
    struct node *link;
};

void reverse() {
    struct node *p = first,
                *q = NULL,
                *r;

    while (p != NULL) {
        r = q;
        q = p;
        p = p->link;
        q->link = r;
    }
    first = q;
}

Gibt es eine andere Alternative, um die verknüpfte Liste umzukehren? Was wäre die beste Logik, um eine einfach verknüpfte Liste in Bezug auf die Zeitkomplexität umzukehren?

Ich hasse es, der Überbringer schlechter Nachrichten zu sein, aber ich glaube nicht, dass Ihre Drei-Zeiger-Lösung wirklich funktioniert. Als ich es im folgenden Testrahmen verwendete, wurde die Liste gemäß der folgenden Ausgabe auf einen Knoten reduziert:

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

Sie erhalten keine bessere Zeitkomplexität als Ihre Lösung, da es O (n) ist und Sie jeden Knoten besuchen müssen, um die Zeiger zu ändern, außer Ihnen kann Machen Sie ganz einfach eine Lösung mit nur zwei zusätzlichen Zeigern, wie im folgenden Code gezeigt:

#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;
    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.
        struct node *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;
}

Dieser Code gibt aus:

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

was ich denke, ist das, wonach Sie gesucht haben. Es kann dies tatsächlich tun, sobald Sie es geladen haben first in den Zeiger, der die Liste durchläuft, können Sie wiederverwenden first nach Belieben.

Hier ist der Code dazu eine einfach verkettete Liste in C umkehren.

Und hier ist es unten eingefügt:

// reverse.c

#include <stdio.h>
#include <assert.h>

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

void spec_reverse();
Node *reverse(Node *head);

int main()
{
    spec_reverse();
    return 0;
}

void print(Node *head) {
    while (head) {
        printf("[%d]->", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

void spec_reverse() {
    // Create a linked list.
    // [0]->[1]->[2]->NULL
    Node node2 = {2, NULL};
    Node node1 = {1, &node2};
    Node node0 = {0, &node1};
    Node *head = &node0;

    print(head);
    head = reverse(head);
    print(head);

    assert(head == &node2);
    assert(head->next == &node1);
    assert(head->next->next == &node0);

    printf("Passed!");
}

// Step 1:
//
// prev head  next
//   |    |    |
//   v    v    v
// NULL  [0]->[1]->[2]->NULL
//
// Step 2:
//
//      prev head  next
//        |    |    |
//        v    v    v
// NULL<-[0]  [1]->[2]->NULL
//
Node *reverse(Node *head)
{
    Node *prev = NULL;
    Node *next;

    while (head) {
        next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }

    return prev;
}

Robert Sedgewick, “Algorithmen in C“, Addison-Wesley, 3. Auflage, 1997, [Section 3.4]

Falls es sich nicht um eine zyklische Liste handelt, ist NULL die letzte Verknüpfung.

typedef struct node* link;

struct node{
    int item;
    link next;
};

/* you send the existing list to reverse() and returns the reversed one */

link reverse(link x){
    link t, y = x, r = NULL;
    while(y != NULL){
        t = y->next;
        y-> next = r;
        r = y;
        y = t;
    }
    return r;
}

Ja. Ich bin sicher, Sie können dies genauso tun, wie Sie zwei Nummern tauschen können, ohne eine dritte zu verwenden. Setzen Sie einfach die Zeiger auf int/long und führen Sie die XOR-Operation ein paar Mal aus. Dies ist einer dieser C-Tricks, die eine lustige Frage darstellen, aber keinen praktischen Wert haben.

Können Sie die O(n)-Komplexität reduzieren? Nein nicht wirklich. Verwenden Sie einfach eine doppelt verknüpfte Liste, wenn Sie glauben, dass Sie die umgekehrte Reihenfolge benötigen.