在不使用任何指针的情况下反转单向链表

Question

当我说不使用任何指针时，我的意思是我们仍然使用“next”指针字段来遍历列表，但在反转链表时不会更改它们。

据我所知，似乎有办法做到这一点：

• 一种方法是在不改变指针本身的情况下反转节点中的数据。
• 第二种方法是创建一个与原始链表相反的新链表。

如果有人能帮助我了解如何使用第一种方法，我将不胜感激。也欢迎其他方法。

Answer 1

今天在工作中，我不断地回到这个问题试图弄明白它。我发现你的限制有点令人困惑，因此“你试过魔法吗？” 评论。最终我越过了街区......

它可能有助于可视化问题。让我们从 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 开始并继续前进，直到 node->next 指向现在保存数据 A 的节点。

B C D E F G

并交换它们：

G C D E F B
  F D E C
    E D 

然而，我仍然对重复单步执行列表的想法感到不舒服——即使在过程的每次迭代中单步执行的范围都会缩小。如果我们有一个 LIFO（后进先出）或其他已知的堆栈怎么办？

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

list_private_reverse 只调用与列表中的元素一样多的次数。