如何仅使用两个指针来反转单链表？
如何仅使用两个指针来反转单链表？
提问于 2009-11-26 12:34:26
我想知道是否存在只使用两个指针来反转单链表的逻辑。
下面的代码使用三个指针(即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;
}是否有其他替代方案可以反转链表？就时间复杂度而言，反转单链表的最佳逻辑是什么？
回答 36
Stack Overflow用户
回答已采纳
发布于 2009-11-26 13:28:11
还有别的选择吗？不，这就像它得到的一样简单，并且没有根本不同的方法。这个算法已经是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;
}Stack Overflow用户
发布于 2009-11-26 13:46:21
我讨厌成为坏消息的传播者，但我不认为你的三分球解决方案真的有效。当我在下面的测试工具中使用它时，列表减少到一个节点，如以下输出所示：
==========
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, *nxtNode;
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.
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。
Stack Overflow用户
发布于 2010-12-14 15:18:02
#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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1801549
复制相关文章
相似问题
腾讯云开发者
