java - 重新排列链表的节点，例如奇数 inode 最后出现

Question

这是我在网站上发现的关于使用 LinkedList 的问题:

Write a method shift that rearranges the elements of a list of integers by moving to the end of the list all values that are in odd-numbered positions and otherwise preserving list order. For example, suppose a variable list stores the following values:

[0, 1, 2, 3, 4, 5, 6, 7]

The call of list.shift(); should rearrange the list to be:

[0, 2, 4, 6, 1, 3, 5, 7]

In this example the values in the original list were equal to their positions and there were an even number of elements, but that won't necessarily be the case. For example, if list had instead stored the following:

[4, 17, 29, 3, 8, 2, 28, 5, 7]

Then after the call list.shift(); the list would store:

[4, 29, 8, 28, 7, 17, 3, 2, 5]

Notice that it doesn't matter whether the value itself is odd or even. What matters is whether the value appears in an odd index (index 1, 3, 5, etc). Also notice that the original order of the list is otherwise preserved. You may not construct any new nodes and you may not use any auxiliary data structure to solve this problem (no array, ArrayList, stack, queue, String, etc). You also may not change any data fields of the nodes; you must solve this problem by rearranging the links of the list.

我首先很难理解这一点。在第一个例子中， [0、1、2、3、4、5、6、7]

move(index 1) will give [0,2,3,4,5,6,7,1]
move(index 3) will give [0,2,3,5,6,7,1,4]

我已经打破了预期的转变。我不清楚这个问题。 关于这个问题以及如何解决这个问题的提示将非常有帮助。

更新:通过理解以下答案实现了这一点:

public void shift() {
    if (front==null)
        return;
  
    ListNode curr = front;
    ListNode temp = curr.next;
    while (curr.next!=null && curr.next.next != null) {
        curr.next = curr.next.next;
        curr = curr.next;
        temp.next = curr.next;
    }
    curr.next = temp;
    temp.next = null;
}

input: [3, 3, 3, 3, 4]  
expected output: front -> [3] -> [3] -> [4] -> [3] -> [3]
my output: front -> [3] -> [3] -> [4] -> [3]

input: [0, 1, 2, 3, 4, 5, 6, 7]
expected output: front -> [0] -> [2] -> [4] -> [6] -> [1] -> [3] -> [5] -> [7]
expected output: front -> [0] -> [2] -> [4] -> [6] -> [1]

从我的输出中可以明显看出，我没有正确地重新链接临时节点。即临时节点没有得到更新。但我不知道为什么？

Answer 1

您的想法基本上是在每次移动后将索引重新计算到列表中。

他们真正考虑的是将列表中的所有其他项目按原样移动。

预期的困难只是跟踪何时停止重新排列元素。您想要在最初是列表中最后一个节点之后停止，但如果您以最明显的方式执行此操作，那么当您到达那里时，该节点将不再是列表中的最后一个节点。

微妙的提示:即使假设一个单向链表无法直接找到最后一个节点，您仍然可以只遍历一次链表来完成这项工作。

这样做有点棘手。在遍历第一个列表时，不是将每个节点都添加到原始列表的末尾，而是在遍历原始列表时将这些节点放在单独的临时列表中。当您到达原始列表的末尾时，然后通过将原始列表末尾的空指针更改为指向临时列表的开头(并且由于您已经到达终点，您将临时列表的最后一个节点中的“下一个”指针设置为 NULL)。

这对于数组来说通常是不切实际的，因为您暂时需要额外的存储空间来存储数组中的一半元素。然而，对于链表，您只需要两个额外的指针:一个指向临时列表的开头，另一个指向临时列表中的最后一个节点。