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

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

还有其他选择&nbsp;不，这很简单，并没有根本不同的方式。这个算法已经是O（n）时间了，你不能比这更快，因为你必须修改每个节点。看起来您的代码在正确的轨道上，但它在上面的表单中并不完全正常。这是一个工作版本：#include&nbsp;<stdio.h>typedef&nbsp;struct&nbsp;Node&nbsp;{ &nbsp;&nbsp;char&nbsp;data; &nbsp;&nbsp;struct&nbsp;Node*&nbsp;next;}&nbsp;Node;void&nbsp;print_list(Node*&nbsp;root)&nbsp;{ &nbsp;&nbsp;while&nbsp;(root)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;printf("%c&nbsp;",&nbsp;root->data); &nbsp;&nbsp;&nbsp;&nbsp;root&nbsp;=&nbsp;root->next; &nbsp;&nbsp;} &nbsp;&nbsp;printf("\n");}Node*&nbsp;reverse(Node*&nbsp;root)&nbsp;{ &nbsp;&nbsp;Node*&nbsp;new_root&nbsp;=&nbsp;0; &nbsp;&nbsp;while&nbsp;(root)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;Node*&nbsp;next&nbsp;=&nbsp;root->next; &nbsp;&nbsp;&nbsp;&nbsp;root->next&nbsp;=&nbsp;new_root; &nbsp;&nbsp;&nbsp;&nbsp;new_root&nbsp;=&nbsp;root; &nbsp;&nbsp;&nbsp;&nbsp;root&nbsp;=&nbsp;next; &nbsp;&nbsp;} &nbsp;&nbsp;return&nbsp;new_root;}int&nbsp;main()&nbsp;{ &nbsp;&nbsp;Node&nbsp;d&nbsp;=&nbsp;{&nbsp;'d',&nbsp;0&nbsp;}; &nbsp;&nbsp;Node&nbsp;c&nbsp;=&nbsp;{&nbsp;'c',&nbsp;&d&nbsp;}; &nbsp;&nbsp;Node&nbsp;b&nbsp;=&nbsp;{&nbsp;'b',&nbsp;&c&nbsp;}; &nbsp;&nbsp;Node&nbsp;a&nbsp;=&nbsp;{&nbsp;'a',&nbsp;&b&nbsp;}; &nbsp;&nbsp;Node*&nbsp;root&nbsp;=&nbsp;&a; &nbsp;&nbsp;print_list(root); &nbsp;&nbsp;root&nbsp;=&nbsp;reverse(root); &nbsp;&nbsp;print_list(root); &nbsp;&nbsp;return&nbsp;0;}

Answer 2

#include&nbsp;<stddef.h>typedef&nbsp;struct&nbsp;Node&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;struct&nbsp;Node&nbsp;*next; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;data;}&nbsp;Node;Node&nbsp;*&nbsp;reverse(Node&nbsp;*cur)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;*prev&nbsp;=&nbsp;NULL; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(cur)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Node&nbsp;*temp&nbsp;=&nbsp;cur; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cur&nbsp;=&nbsp;cur->next;&nbsp;//&nbsp;advance&nbsp;cur &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp->next&nbsp;=&nbsp;prev; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;prev&nbsp;=&nbsp;temp;&nbsp;//&nbsp;advance&nbsp;prev &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;prev;}