如何交换循环链表的两半?

Question

我正在用循环链表解决这个代码挑战:

在CLList类中，编写一个名为swapHalf()的函数，将列表的前半部分交换为后半部分。你应该投保所有的险种。

例子:

之前[v, w t j, q, o, w,年代,w t]

swapHalf()

后[o, w,年代,w t v, w, t, j, q)

我只能涵盖列表有0或2个元素的情况。但对于后者，列表会丢失一个元素，我不知道如何覆盖任何循环列表大小:

public void swapHalf() {
CharNode cn;
if (tail == null) {
return;
} else if (tail == tail.next.next) {
cn = tail;
cn.setNext(tail);
cn.next.setNext(tail.next);
}
}

Answer 1

不需要调用setNext。不应该改变任何节点——所有的链接都可以保持不变。唯一需要改变的是tail引用的内容。

可以使用两个遍历列表的节点引用，但其中一个移动速度是另一个的两倍。当快的一方完成了一个完整的循环时，另一方必然会完成一半的循环。然后，唯一要做的就是将tail引用设置为该节点。

public void swapHalf() {
if (tail == null || tail.next == tail) { // 0 or 1 node
return;
}
CharNode fast = tail.next.next;
CharNode origTail = tail;
tail = tail.next
while (fast != origTail && fast.next != origTail) {
fast = fast.next.next;
tail = tail.next;
}
}