java - 链表的功能

Question

为了准备实验，我收到了以下作业。我真诚地试图理解，但这对我来说没有意义。

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

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 .