shift every other elements of linkedlist (in place) to end of linkedlist in java

Question

The questions is as follows: given a linked list, shift the alternate indices to back of list

for ex:

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

As you can see from the expected output, elements at odd positions (indices) are moved to back of linkedlist. I tried to implement this; I could get the odd indices removed and but they are not linking to the end of list.

my Code is here:

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


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

I need some assistance here

P.S: No Auxiliary storage must be used. No other containters!!!. so this is an in-place re-arrangement

Answer 1

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

Answer 2

You will need to store a reference to the back of the list. Then, traverse the list, and add every other element to the end.

public void shift() {
    if (front == null)
        return;

    ListNode curr = front;
    ListNode temp;
    ListNode back = front;
    while (back.next != null)
        back = back.next;
    ListNode originalBack = back;

    while (curr.next != originalBack){
        temp = curr.next;
        curr.next = curr.next.next;
        temp.next = null;
        back = back.next = temp;
        curr = curr.next;
    }
}

Answer 3

While traversing, pop every other item out, and link those together to make a second list. When you reach the end of your first list, append the second list. I'm on my ipad so I can't code but will post once I get online.

Answer 4

It can be done in this way my friend, hope this helps you

public void shift(){
    if (front==null) return;

    ListNode curr=front;
    ListNode temp=curr.next;
    while (curr.next!=null){
        curr.next=curr.next.next;
        curr=curr.next;

     }
     curr.next=temp;

}




after 1st pass 0->2, 
after 2nd pass 1->3,
after 3rd pass 2->4, 
after 4th pass 3->5,
after 5th pass 4->6, 
after 6th pass 5->7,

and then 7->next is null so we assign tmp to it which is pointing to 1.