我想知道是否存在一种逻辑可以仅使用两个指针来反转单链表。
以下方法使用三个指针，分别为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;
}
我很不愿意成为传递坏消息的人，但我认为您提出的三指针解决方案实际上并不起作用。当我在下面的测试环境中使用它时，列表被缩减为一个节点，如下所示:
==========
4
3
2
1
0
==========
4
==========
由于您的解决方案的时间复杂度为O(n)，而且必须访问每个节点才能更改指针，因此您不会获得比您的解决方案更好的时间复杂度，但是您可以很容易地使用仅两个额外指针的解决方案，如下面的代码所示：
#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;
}
这段代码输出：
==========
4
3
2
1
0
==========
0
1
2
3
4
==========
我认为这就是你所需要的。实际上它可以做到这一点，因为一旦你将first加载到遍历列表的指针中，你可以随意重复使用first。
first 指针使得该解决方案只需要使用 2 个 额外 指针，但总共仍需要 3 个指针。 - Kevin Kiblerfirst 顶部有两个 额外 指针。就像 OP 的三指针解决方案中有 first、p、q 和 r 一样。 - paxdiablo#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;
}
以下是用 C 语言翻转单向链表的代码，可在此处查看。
下面是代码的复制粘贴：
// 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;
}
罗伯特·塞奇威克，《C语言算法》（第三版），Addison-Wesley出版社，1997年，[第3.4节]
In case that is not a cyclic list ,hence NULL is the last link.
typedef struct node* link;结构体节点(node)：
struct node{ int item; link next; };
/* 输入一个已存在的链表到reverse()函数，返回倒序后的链表 */
链表逆序函数(link reverse)： 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; }
仅供娱乐（虽然尾递归优化应该能防止它耗尽所有的栈）：
Node* reverse (Node *root, Node *end) {
Node *next = root->next;
root->next = end;
return (next ? reverse(next, root) : root);
}
root = reverse(root, NULL);
Node* reverselist( )
{
Node *first = NULL; // To keep first node
Node *second = head; // To keep second node
Node *track = head; // Track the list
while(track!=NULL)
{
track = track->next; // track point to next node;
second->next = first; // second node point to first
first = second; // move first node to next
second = track; // move second node to next
}
track = first;
return track;
}
是的。我确定你可以用和不使用第三个变量交换两个数字一样的方法来完成这个操作。只需将指针强制转换为int/long类型，然后执行几次异或操作即可。这是那些有趣但没有实际价值的C技巧之一。
你能减少O(n)的复杂度吗？实际上不能。如果你认为需要反向排序，只需使用双向链表即可。
以下是Java语言的简化版本。它只使用了两个指针curr和prev
public void reverse(Node head) {
Node curr = head, prev = null;
while (head.next != null) {
head = head.next; // move the head to next node
curr.next = prev; //break the link to the next node and assign it to previous
prev = curr; // we are done with previous, move it to next node
curr = head; // current moves along with head
}
head.next = prev; //for last node
}
Node *pop (Node **root)
{
Node *popped = *root;
if (*root) {
*root = (*root)->next;
}
return (popped);
}
void push (Node **root, Node *new_node)
{
new_node->next = *root;
*root = new_node;
}
Node *reverse (Node *root)
{
Node *new_root = NULL;
Node *next;
while ((next = pop(&root))) {
push (&new_root, next);
}
return (new_root);
}