Rearrange a Linked List in zig-zag fashion




Rearrange a Linked List in Zig-Zag fashion

Given a linked list, rearrange it such that converted list should be of the form a < b > c < d > e < f .. where a, b, c.. are consecutive data node of linked list. Examples :
Input:  1->2->3->4
Output: 1->3->2->4 

Input:  11->15->20->5->10
Output: 11->20->5->15->10



Code:

package linkedlist;

import linkedlist.RerverseKnodes.Node;

/*
 * author: Nivetha G
 */

public class RearrageListZigZagFashion {


    Node head = null;


    class Node{

        int data;
        Node next;

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

    void insert(int data){

        Node new_node = new Node(data);

        if(head == null){
            head = new_node;
            return;
        }

        Node last = head;

        while(last.next != null){
            last = last.next;
        }

        last.next = new_node;

    }

    static void printlist(Node head) {

        Node temp = head;

        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println("");
    }

    static void rearrange(Node head){

        Node curr = head;

        boolean flag = true;

        while(curr!= null && curr.next != null){

            if(flag && curr.data > curr.next.data || !flag && curr.data < curr.next.data ){

                int temp = curr.data;
                curr.data = curr.next.data;
                curr.next.data = temp;

            }

            flag = !flag;
            curr = curr.next;

        }
       
        printlist(head);



    }


    public static void main(String[] args){

        RearrageListZigZagFashion list = new RearrageListZigZagFashion();
       
        list.insert(4);
        list.insert(3);
        list.insert(7);
        list.insert(8);
        list.insert(6);
        list.insert(2);
        list.insert(1);
       
        printlist(list.head);
       
        rearrange(list.head);

  }

}

Output:

4 3 7 8 6 2 1
3 7 4 8 2 6 1

Comments

Popular posts from this blog

Rearrange Array in Maximum-Minimum form

Second Largest Element

Check if a number is a power of another number