当我说不使用任何指针时，我的意思是我们仍然使用"下一个"指针字段来遍历列表，但在反转链表时不会更改它们。
据我所知，似乎有办法做到这一点：
- 一种方法是在不改变指针本身的情况下反转节点中的数据
- 第二种方法是创建一个新的链表，该链表与原始链表相反
如果有人能帮助我如何进行第一种方法，我将不胜感激。其他方法也受到欢迎。
今天在工作中，我不断地回到这个问题上，试图弄清楚它的意义。我发现你的限制有点令人困惑，因此我问"你试过魔术吗？"议论最终我越过了障碍。。。
将问题形象化可能会有所帮助。让我们从Julio Moreno代码中的想法开始，稍微简化一下：遍历列表，用尾部数据交换每个节点数据。
A B C D E
E B C D A
E A C D B
E A B D C
E A B C D
E D B C A
E D A C B
E D A B C
E D C B A
（在工作中，我得出结论，这个过程不会成功，但现在我有更多的时间可以看到它成功了）。如果我们仔细观察他的函数，我们可以看到，除此之外，它也可以递归工作。我并不热衷于可视化从for循环调用的递归函数。这一过程显然不会赢得任何效率奖。
因此，让我们看看如果我们不想限制自己不修改节点位置，我们可以做什么：
A B C D E
B C D E A
C D E B A
D E C B A
E D C B A
这里我们取尾节点E，记住它。我们现在取节点A，将其插入E之后，然后取节点B，将其再次插入E之后但在A之前，逐步完成整个列表，在E之后立即插入，直到E是列表的第一个节点（头）。它有效，但我们不允许这样做。
让我们更进一步，假设它是一个双重链接的列表，我们维护两个指针，一个在列表的开头，另一个在末尾，我们交换两者的数据，然后分别递增一个和递减另一个。
A B C D E
E B C D A
E D C B A
已完成！
那么，我们如何用一个单独的链表来做到这一点呢？我们需要知道什么？我们如何在后退的同时又向前迈进？
让我们从如何通过遍历整个列表来获取最后一个节点开始。
A B C D E F G H
并交换它们：
H B C D E F G A
然后，如果我们记住我们交换的两个节点的数据，我们可以从B开始，一直走到节点->下一个指向现在持有数据A的节点。
B C D E F G
并交换它们：
G C D E F B
F D E C
E D
然而，我仍然对重复遍历列表的想法感到不舒服——即使在过程的每次迭代中，遍历的范围都会缩小。如果我们有后进先出法（后进先出）或众所周知的堆栈呢？
A B C D E F G H
B C D E F G H ... A
C D E F G H ... B
D E F G H ... C
E F G H ... D
F G H ... E
G H ... F
H ... G...F...E...D...C...B...A
但这是辅助数据存储，我们不允许这样做，但不难看出如何用递归函数调用和链表实现LIFO。那么，我们如何使用递归函数调用和链表来向前和向后迈进呢？我们不需要一个额外的参数吗？当我们到达列表的末尾时，我们仍然需要知道它是如何开始的。
A B C D E F G H
A,B ^ return 0
A,C ^ return 0
A,D ^ return 0
A,E ^ swap D E done, return 0
A,F ^ swap C F return D
A,G ^ swap B G return C
A,H ^ swap A H return B
我还没有真正测试过这一点来证明它，所以它可能是错误的。我现在就去测试它，如果需要的话可以发布代码。希望我不必编辑这篇文章说它不起作用；-）
编辑：可以确认它有效。
static lnode* list_private_reverse(lnode* list, lnode* node)
{
lnode* next = node->next;
if (next)
{
lnode* swap = list_private_reverse(list, next);
if (swap)
{
int c = swap->c;
swap->c = node->c;
node->c = c;
if (swap->next == node || swap->next->next == node)
return 0;
return swap->next;
}
return 0;
}
else
{
int c = node->c;
node->c = list->c;
list->c = c;
}
return list->next;
}
lnode* list_reverse(lnode* list)
{
list_private_reverse(list, list);
return list;
}
CCD_ 1的调用次数仅与列表中有元素的次数一样多。
这个问题与其他反转问题没有太大区别。一种解决方案是遍历列表，并将每个数据项放入一个数组中。然后，再次遍历列表，但从数组的末尾开始，然后用数组中的值按相反的顺序覆盖列表数据。
for (n in list) arr[i++] = n->data
for (n in list) n->data = arr[--i]
如果不允许存储任何内容，那么递归也不可用，因为它充当了存储反向列表的辅助数组。然后，一个愚蠢的解决方案是实现列表的随机访问接口：
Node * nth_list_item (Node *list, int n);
它返回列表的第n个项。然后，使用这个接口反转列表，可以像访问数组一样访问它（当然会有时间限制）。反转不再需要O（n）时间，而是现在的O（n2）。
如果递归是可以的，那么为了满足"不存储元素"要求的精神，您需要递归遍历列表，然后在展开时反转列表。这可以通过允许递归调用的另一个参数提供在递归调用从末尾展开时遍历列表开头所需的指针来实现。此实现在每次递归调用中不使用额外的局部变量，只使用参数中提供的变量。
void swap_left (node *a, node *b, int tmp) {
a->data = b->data;
b->data = tmp;
}
void reverse_recursively (node *cur, node **tail) {
if (cur) {
reverse_recursively(cur->next, tail);
if (*tail) {
swap_left(cur, *tail, cur->data);
if (cur != *tail) *tail = (*tail)->next;
if (cur == *tail) *tail = 0;
}
}
}
void reverse (node *list) {
reverse_recursively(list, &list);
}
如果允许我们在使用递归时侵犯"不存储元素"要求的精神，那么就有了一个更直接（但更占用空间）的解决方案。基本上，反向链表的副本可以在递归遍历时创建。当到达末尾时，可以再次遍历列表，从反向副本中复制元素。
#define make_node(n, d) (node){ n, d }
void reverse_recursively (node *list, node *cur, node copy) {
if (!cur) {
for (cur = © cur; cur = cur->next, list = list->next) {
list->data = cur->data;
}
return;
}
reverse_recursively(list, cur->next, make_node(©, cur->data));
}
void reverse (node *list) {
if (list == 0) return;
reverse_recursively(list, list->next, make_node(0, list->data));
}
类似的操作会奏效，第一个函数实际上并没有切换（很抱歉名称混淆），它的工作原理很像插入算法，它接受列表的最后一个元素并将其插入到"当前"位置。我严重怀疑这种算法的效率：
typedef struct node node;
struct node {
node *next;
void *value;
};
typedef node linked_list;
node *switch_with_end(node *c)
{
if (c->next) {
node *t = switch_with_end(c->next);
void *temp = t->value;
t->value = c->value;
c->value = temp;
}
return c;
}
void reverse_list(linked_list *l)
{
node *c;
for (c = l; c->next; c = c->next)
switch_with_end(c);
}
@ames Morris——解释得很好。但是你的代码和我的代码有什么区别。。。
最多使用2个指针。。。
Node* reverseLL (Node *curr, Node *prev)
{
Node *nxt = NULL;
if (curr)
{
nxt = curr->next;
curr->next = prev;
curr = reverseLL (nxt, curr);
}
else
return prev;
}
void reverseList (Node **head)
{
Node *curr = *head;
Node *prev = NULL;
curr = reverseLL (curr, prev);
*head = curr;
}
实现一个堆栈并使用它来反转链表。堆栈是先进先出的数据结构（FILO）。在第一次迭代中将链表的内容推送到堆栈上，然后在第二次迭代中将它们弹回到列表中。
一旦实现了一个堆栈，它就可以很好地解决大部分反转问题。
当然，你使用了更多的空间，这意味着它没有到位。
//Reversal of linked list without using pointers.
void reverseList(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
reverseList(head->next);
//save the current value
int val = head->val;
ListNode *temp = head;
// shift all the values to the left
while(temp->next != NULL)
{
temp->val = temp->next->val;
temp = temp->next;
}
// assign the save value at the end of the list
temp->val = val;
return;
}