Zig Zag Concept in Java using Linked List

 import java.util.*;

class Node {

    int data;

    Node next;

   

    Node(int data) {

        this.data = data;

        this.next = null;

    }

}

class LinkedList {

    Node head;

    public void addFirst(int data) {

        Node newNode = new Node(data);

        newNode.next = head;

        head = newNode;

    }

    public void printList() {

        Node temp = head;

        while(temp != null) {

            System.out.print(temp.data + " -> ");

            temp = temp.next;

        }

        System.out.println("null");

    }

    public void zigZag() {

    // find mid

    Node slow = head;

    Node fast = head.next;

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

        slow = slow.next;

        fast = fast.next.next;

    }

    Node mid = slow;

    // reverse 2nd half

    Node curr = mid.next;

    mid.next = null; // tod diya yahan pe

    Node prev = null;

    Node next;

    while(curr != null) {

        next = curr.next;

        curr.next = prev;

        prev = curr;

        curr = next;

    }

    Node left = head;

    Node right = prev;

    Node nextL, nextR;

    // alt merge - zig-zag merge

    while(left != null && right != null) {

        nextL = left.next;

        left.next = right;

        nextR = right.next;

        right.next = nextL;

        left = nextL;

        right = nextR;

    }

}

}

public class Main {

   

    public static void main(String[] args) {

        LinkedList ll = new LinkedList();

        ll.addFirst(6);

        ll.addFirst(5);

        ll.addFirst(4);

        ll.addFirst(3);

        ll.addFirst(2);

        ll.addFirst(1);

       

       

        ll.printList();

        ll.zigZag();

        ll.printList();

    }

}

OUTPUT:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null