将链表的头部移动到尾部

Question

我需要用 Java 编写一个方法，将链表中的第一个元素移动到最后一个位置。

为了实现这一点，我相信我必须设置一个节点来引用 head 之后的第一个元素，然后将下一个节点设置为 null。我尝试用我的方法执行此操作，但是运行该方法时，输出不正确。

我的课程的其余部分很可能太大，无法发布在这里，但我认为我只需要帮助概念化如何将第一个元素移动到列表的末尾。

我写的方法是：

public void moveFirstToEnd() {
    if (head.next == null) {
        throw new NoSuchElementException();
    } 

    Node node = head.next;
    node.next = null;
    head.next = node;
    tail.next = node;
    tail = node;
}

Answer 1

您想要删除列表的头部并将其作为新的尾部。您应该在脑海中弄清楚如何做到这一点，代码将是其逻辑表示。

1. 删除列表的头部。新的头部成为下一个项目。
2. 被移除的项目现在是独立的；之后就什么都没有了。
3. 将节点放在链表的末尾。新的尾部成为该节点。

正如您所看到的，您现在的代码并没有完全做到这一点。一次完成一个步骤：

所以，第 1 步：

Node node = head;
head = head.next; // <- remove head, new head becomes next item

然后，第2步：

node.next = null; // there's nothing after it.

最后，第 3 步：

tail.next = node; // <- add to end of list
tail = node; // <- becomes new end of list

或者，如果你更愿意想象它：

Node node = head:

+------+    +------+    +------+    +------+
| head |--->|      |--->|      |--->| tail |
+------+    +------+    +------+    +------+
  node

head = head.next:

+------+    +------+    +------+    +------+
|      |--->| head |--->|      |--->| tail |
+------+    +------+    +------+    +------+
  node

node.next = null:

+------+    +------+    +------+    +------+
|      |    | head |--->|      |--->| tail |
+------+    +------+    +------+    +------+
  node

tail.next = node:

            +------+    +------+    +------+    +------+
            | head |--->|      |--->| tail |--->|      |
            +------+    +------+    +------+    +------+
                                                  node

tail = node:

            +------+    +------+    +------+    +------+
            | head |--->|      |--->|      |--->| tail |
            +------+    +------+    +------+    +------+
                                                  node

顺便说一句，如果您已经定义了popFront（或其他）和/或append操作，请不要忘记您也可以使用它们；没有意义重复代码：

Node node = popFront(); // if you have this
append(node); // if you have this