将链表的头移到尾

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