如何仅使用两个指针反转单链表？

Question

如何仅使用两个指针反转单链表？我想知道是否存在一些逻辑来仅使用两个指针来反转链表。以下是用于逆转使用三个指针即单链表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;}还有其他替代方法来反转链表吗？在时间复杂度方面，逆转单链表的最佳逻辑是什么？

Answer 1

还有其他选择 不，这很简单，并没有根本不同的方式。这个算法已经是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;}

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;}