如何扭转只用两个指针一个单向链表？ [英] How to reverse a singly linked list using only two pointers?

问题描述

我是否存在一些逻辑，只用两个三分球扭转链表会被怀疑。

I would be wondered if there exists some logic to reverse the linked list using only two pointers.

时，用于反向使用三个指针的单链表以下即P，Q，R：

The following is used to reverse the single linked list using three pointers namely 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;
    }
    q = first;
}

是否有其他替代扭转链表？这将是扭转单向链表最好的逻辑，在时间复杂度方面？

Is there any other alternate to reverse the linked list? what would be the best logic to reverse a singly linked list, in terms of time complexity?

推荐答案

什么替代？不，这是因为它得到一样简单，而且也做不从根本上，不同的方式。该算法已经是O（n）的时间，你不能得到任何比这更快，因为你必须修改每一个节点。

Any alternative? No, this is as simple as it gets, and there's no fundamentally-different way of doing it. This algorithm is already O(n) time, and you can't get any faster than that, as you must modify every node.

它看起来像你的code是在正确的轨道，但它并不完全工作在形式上面。这里有一个工作版本：

It looks like your code is on the right track, but it's not quite working in the form above. Here's a working version:

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

这篇关于如何扭转只用两个指针一个单向链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！