Rearrange nodes of linked list such as odd numbered index-nodes appear last

Question

Here is a question that I found on website for problems using 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.

I am having difficulty understanding this first. In the first example, [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]

I have already broken the shift that is expected. I do not understand the problem clearly. Tips on this problem and how to approach this would be very helpful.

Update: implemented this from understanding the answer below:

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]

As it is evident from my output, I am not re-linking the temp nodes properly. i.e temp nodes is not getting updated. but I don't know why?

Answer 1

Try this: the code is self-explanatory: If you do not understand, post comment, I will clarify

public void switchPairs() {
    if (front != null && front.next != null) {
        ListNode current = front.next;
        front.next = current.next;
        current.next = front;
        front = current;
        current = current.next;

        while (current.next != null && current.next.next != null) {
            ListNode temp = current.next.next;
            current.next.next = temp.next;
            temp.next = current.next;
            current.next = temp;
            current = temp.next;
        }
    }
}