java - 将链表的头部移动到尾部

Question

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

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

我所拥有的类(class)的其余部分很可能太大而无法在此处发布，但我认为我只需要帮助概念化如何将第一个元素移动到列表的末尾。

我写的方法是:

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

然后，第二步:

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