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

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

## 1 Answer

0 votes
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.

package com.ds.linkedlist;

public class RearrangeListEvenOddPosition {

Node head;
/**
* @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();
Node relist = rearrangedList.rearrangeListEvenOdd(list.head);
rearrangedList.head = relist;
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);
if(head == null){
head = newNode;
}else{
Node curr = head;
while(curr.next != null){
curr = curr.next;
}
curr.next = newNode;
}
}

public void print(){
if(head==null)
return;
Node curr = head;
while(curr != null){
System.out.print(curr.data + " ");
curr = curr.next;
}
}

}
Output:-
List:
1 2 3 4 5 6 7
Rearranged List:
1 3 5 7 2 4 6
by (4.3k points)