从单链表中提取前 n 个元素

Question

我正在尝试编写一个接受整数 n 和 returns 一个新列表的方法，该列表包含其当前对象 List 的前 n 个元素，其顺序与它们在当前对象中出现的顺序相同列表。

下面提供了我的解决方案：

public List firstNelements(int n) {
    List newList = newList();
    Node travel = head, last = null, newNode;
    int counter = 0;
    while (counter < n && travel != null) {
        newNode = new Node();
        newNode.data = travel.data;

        if (last == null)
            last = newList.head = newNode;
        else last = last.next = newNode;

        counter++;
        travel = travel.next;
    }
    return newList;
}

我了解该方法首先声明一个新列表。从那里，它声明 "travel" 节点，该节点用于遍历整个当前列表。另外，我相信 "last" 只是为了跟踪当前对象中的最后一个节点。

while循环的第一部分我也看懂了；但是，我不明白为什么条件

if (last == null)
            last = newList.head = newNode;
        else last = last.next = newNode;

存在。代码首次执行时节点 "last" 为空，因此在第一次迭代中，我猜测我们将 newNode 设置为新列表的头部。但为什么我们也要最后更新呢？这是否意味着 "last" 正在跟踪新列表中的最后一个节点？我也不知道 "else" 语句在这里做什么。

我已经遍历了列表 {1, 2, 3}，其中 n = 2。但是，我仍然无法理解它。 while 循环的其余部分（在这个条件之后）对我来说很有意义。

Answer 1

if (last == null) {
    last = newList.head = newNode;
} else {
    last = last.next = newNode;
}

如果 last 为 null，则将 newList.head 设置为 newNode，然后将 last 设置为 newNode。
如果 last 不为空，将 last.next 设置为 newNode，然后将 last 设置为 newNode。

每次迭代创建 newNode = new Node() 并将 newNode.data 分配给 travel.data。

假设迭代 1 创建节点 1，迭代 2 创建节点 2。

在返回的结构中，Node1.next需要是Node2。

当我们处于迭代 2 时，我们已经处理了 Node1，但不知道接下来会发生什么（即 Node1.next 为空）。那么——Node1 怎么知道 "Node1.next" 应该是 "Node2"？

这就是这个条件句的作用。

Answer 2

您必须使用的对象似乎是一个链接列表，即每个 node 都引用列表中的下一个 node。一个节点是特殊的，称为 head。这允许遍历从开始 head 到结束的所有元素（当 .next 是 null 时）。在第一次迭代期间，必须将此 head 设置为在列表中包含一些内容以便稍后迭代。当 last 为 null 时，while 循环是第一次执行。如果这不是第一个循环，则仅设置前一个循环中考虑的 last 节点的 .next 指针，以便在元素之间建立适当的链接。

这是作业吗？也许 Java LinkedList is doing something similar internally. If this not a homework the better approach would be to use existing solutions from the Java Collection framework and e.g. the subList 方法。

从单链表中提取前 n 个元素

Extracting the first n elements from a Singly Linked List

java

linked-list

singly-linked-list