# Rearrange a linked list according to even and odd positioned nodes

42 views
Rearrange a linked list according to even and odd positioned nodes
List:- [1, 2, 3, 4, 5, 6, 7]
Result:- []

See the following running example to rearrange a linked list according to even and odd positioned nodes. For rearranging the linked list which is based on its odd and even position.

public class RearrangeListEvenOddPosition {

/**
* @param args
*/
public static void main(String[] args) {
RearrangeListEvenOddPosition list = new RearrangeListEvenOddPosition();
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(4);
list.insert(5);
list.insert(6);
list.insert(7);
System.out.println("List: ");
list.print();

System.out.println("\nRearranged List: ");
RearrangeListEvenOddPosition rearrangedList = new RearrangeListEvenOddPosition();
rearrangedList.print();

}

/**
* Rearrange the linked list according to its odd and even places
*
* @param list
* @return
*/
private Node rearrangeListEvenOdd(Node list) {
if(list == null)
return list;
//Initialize first node as odd node
Node odd = list;
//Initialize second node as even node
Node even = list.next;
//Connect the even list at the end of odd list.
Node evenFirst = even;
while(true){
if(even == null || odd == null || even.next == null){
odd.next = evenFirst;
break;
}
// Connecting odd nodes
odd.next = even.next;
odd = even.next;
// If there are NO more even nodes after current odd.
if (odd.next == null){
even.next = null;
odd.next = evenFirst;
break;
}

// Connecting even nodes
even.next = odd.next;
even = odd.next;
}
return list;
}

private class Node{
int data;
Node next;
Node(int data){
this.data = data;
}
}

public void insert(int data){
Node newNode = new Node(data);
}else{
while(curr.next != null){
curr = curr.next;
}
curr.next = newNode;
}
}

public void print(){
return;