链表的功能

Question

我准备了下面的实验作业。我真诚地试着去理解，但这对我来说毫无意义。

问题类似于"在执行下面定义的链表上的有趣方法后，哪个给定的解决方案是正确的输出。"注意，我们将下面定义的链表的第一个元素作为参数传递给func -第一个元素也恰好被称为'first'。"

Client code:
var input = first -> r -> e -> d -> i -> v -> i -> d -> e -> r -> null; 
public Node fun(Node x) {
   Node first = x;
   Node magic = null;
   while (first != null) {
      Node second = first.next;
      first.next  = magic; 
      magic       = first;
      first       = second;
   }
   return magic;
}

所以我收集到的是你用链表中的每个节点调用函数，一次一个。所以首先是fun(first)，然后是fun(r)等等。

我有四个备选答案:

first -> v -> i -> r -> e -> d -> null
first -> r -> e -> d -> i -> v -> i -> d -> e -> r -> null
first -> d -> r -> v -> r -> d -> null
first -> d-> e -> r -> i -> v -> i -> r -> e -> d -> null

那么问题是，函数用链表做什么?它是删除节点、交换节点还是两者兼而有之?

Answer 1

从不变量的角度思考。循环的不变量是什么?first是当前节点，而magic是它"左边"的节点。在每个步骤中，您将当前节点的next设置为指向magic。更好的不变量是magic是原始列表的反向部分的头，直到当前(first)节点。然后，您可以意识到该函数将列表反转并返回新列表的头部。所以答案是:r -> e -> d -> i -> v -> i -> d -> e -> r -> first -> null .