Form a list with the elements at odd indices and another list with the elements at even indices. Append the odd list to even list. The time complexity is O(n) and the auxiliary space complexity is O(1).
public void shift() {
if (front == null)
return;
ListNode oddList, even, odd;
oddList = even = odd = front;
oddList = front.next;
while (even.next != null) {
odd.next = even.next;
odd = even.next;
even.next = odd.next;
if(odd.next != null) {
even = odd.next;
odd.next = null;
} else {
odd.next = null;
break;
}
}
if(oddList != null) {
even.next = oddList;
}
//"front" points to the start of the new list.
}