链表程序，输出/函数不确定

Question

我想运行1,2,3,4,5链表的输入。我想知道上面链表的funcA的输出，以及程序实际在做什么。我认为它要么颠倒了链表的顺序，要么旋转了链表中的所有项，比如2,3,4,5,1，这是正确的吗？谢谢你的帮助！

   struct Node {
    int value;
    Node *next;};

Node* funcA(Node* in) {
    Node *out = in;
    while (out->next != nullptr) {
    out = out->next;
    }
    funcB(in)->next = NULL;
    return out;
}

Node* funcB(Node* in) {
   if (in->next != nullptr) {
    funcB(in->next)->next = in;
   }
   return in;
}

Answer 1

为了理解funcA()，我们首先需要理解funcB()。

funcB

简单地颠倒一个列表并返回颠倒的列表的尾部(或原始列表的头部)。它是通过调用自身(递归)来完成的，直到它到达原始列表的尾部。然后，递归开始折叠，并重新分配每个节点的next指针以指向它之前的节点。

funcA

while循环的目标是保存一个指向输入列表尾部的指针out。因此，当前状态为：

List: 1 --> 2 --> 3 --> 4 --> 5 --> NULL
      ^                       ^
      in                     out

然后，它以列表的头部作为参数调用funcB。我们知道funcB将颠倒其给定的列表并返回其最后一个元素。因此，在funcB(in)之后，我们将得到：

List: 1 <--> 2 <-- 3 <-- 4 <-- 5
      ^                        ^
      in                      out

返回值是节点1。所以在funcB(in)->next = NULL之后，我们将得到：

List: NULL <-- 1 <-- 2 <-- 3 <-- 4 <-- 5
               ^                       ^
               in                     out

然后，返回out。因此，总体上- funcA正在获取一个链表，颠倒它并返回指向颠倒的链表5的头部的指针。

当涉及到链表(和一般的指针)时，最好的理解方法是使用铅笔和纸-只需在纸上绘制列表的每个状态和额外的指针，一步一步，直到它变得清晰。