How do I swap the two halves of a circular linked list?

Question

I am working on this code challenge with a circular linked list:

In class CLList, write a function called swapHalf() which swaps the first half of the list by the second half. You should cover all the cases.

Example:

Before [v,w,t,j,q,o,w,s,w,t]

swapHalf()

After [o,w,s,w,t,v,w,t,j,q]

I could only cover the cases where the list has 0 or 2 elements. But for the latter, the list loses an element, and I don't know how to cover for any circular list size:

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

There should be no need to call setNext. No node should be mutated -- all the links can remain the same. The only thing that needs to change is what tail references.

You could use two node references that traverse the list, but with one moving twice as fast as the other. When the fast one has made a full cycle, the other one will by consequence be half way the list. Then the only thing to do is to set the tail reference to that node.

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;
    }
}