Group nodes by their index If there is a singly linked list

Group nodes by their index:

If there is a singly linked list, based on indexes, group all nodes with odd index first followed

by the nodes with even index.

Example:

Given 0->1->2->3->4->5->NULL

return 1->3->5->0->2->4->NULL

Notes:

1, We are talking about the node number(index) and not the value in the nodes.

2, The relative order inside both the even and odd groups should remain as it was in the

input.

3, The first node is considered even, the second node odd and so on ...

If you can solve the above problem easily, you can try to solve it with one more request

again:

solve the problem above “in place”

Note:

You can find the definition of “in place” in

https://en.wikipedia.org/wiki/In-place_algorithm

Code outline:

// Definition for a node.

public class ListNode {

int val;

ListNode next;

ListNode(int x) { val = x; }

}

// solution class

public class Solution {

public ListNode oddEvenList(

ListNode head) {

// please add your code here

}

// Do not need to write the main function, I will test the method

//oddEvenList(ListNode head) by myself.

}

Solution

The idea is to get pointer to the last node of list. And then traverse the list starting from the head node and move the even valued nodes from their current position to end of the list.

Algorithm:
1) Get pointer to the last node.
2) Move all the even nodes to the end.
.a) Consider all even nodes before the first odd node and move them to end.
.b) Change the head pointer to point to the first odd node.
.b) Consider all even nodes after the first odd node and move them to the end.

void oddEvenList(ListNode head)
{
ListNode end = head;
ListNode prev = null;
ListNode curr = head;

/* Get pointer to last ListNode */
while (end.next != null)
end = end.next;

ListNode new_end = end;

// Consider all even ListNodes before getting first odd ListNode
while (curr.data %2 ==0 && curr != end)
{
new_end.next = curr;
curr = curr.next;
new_end.next.next = null;
new_end = new_end.next;
}

// do following steps only if there is an odd ListNode
if (curr.data %2 !=0)
{
head = curr;

// now curr points to first odd ListNode
while (curr != end)
{
if (curr.data % 2 != 0)
{
prev = curr;
curr = curr.next;
}
else
{
/* Break the link between prev and curr*/
prev.next = curr.next;

/* Make next of curr as null */
curr.next = null;

/*Move curr to end */
new_end.next = curr;

/*Make curr as new end of list */
new_end = curr;

/*Update curr pointer */
curr = prev.next;
}
}
}

/* We have to set prev before executing rest of this code */
else prev = curr;

if (new_end != end && end.data %2 == 0)
{
prev.next = end.next;
end.next = null;
new_end.next = end;
}
}

Please let me know in case of any issue