[解決済み] 2つのポインタを使って単一リンクリストを逆引きする方法

質問

2つのポインタだけを使って単一リンクリストを反転させるロジックはないでしょうか。

以下は、3つのポインタを使った単一リンクリストの反転、すなわち 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;
}

リンクリストを逆引きするための他の代替手段はないのでしょうか？ 時間の複雑さの観点から、単一リンクリストをリバースするための最良のロジックは何でしょうか？

どのように解決するのですか?

何か代替案がありますか？ いいえ、これは限りなくシンプルであり、根本的に異なる方法はありません。 このアルゴリズムはすでに O(n) 時間であり、すべてのノードを変更する必要があるため、これ以上速くすることはできません。

あなたのコードは正しい方向に進んでいるように見えますが、上のような形では全く動作していません。 以下は動作するバージョンです。

#include <stdio.h>

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

void print_list(Node* root) {
  while (root) {
    printf("%c ", root->data);
    root = root->next;
  }
  printf("\n");
}

Node* reverse(Node* root) {
  Node* new_root = 0;
  while (root) {
    Node* next = root->next;
    root->next = new_root;
    new_root = root;
    root = next;
  }
  return new_root;
}

int main() {
  Node d = { 'd', 0 };
  Node c = { 'c', &d };
  Node b = { 'b', &c };
  Node a = { 'a', &b };

  Node* root = &a;
  print_list(root);
  root = reverse(root);
  print_list(root);

  return 0;
}