• Register
Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Rearrange a linked list according to even and odd positioned nodes

0 votes
40 views
Rearrange a linked list according to even and odd positioned nodes
List:- [1, 2, 3, 4, 5, 6, 7]
Result:- []
asked Feb 19 in Data Structure And Algorithm by Yogesh Yadev

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
answered Feb 19 by ranju_12 (2,280 points)
...