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

MergeSort using Linked List in Java

 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");

    }

    private Node getMid(Node head) {

        Node slow = head;

        Node fast = head.next;

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

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow; // mid node

    }

    private Node merge(Node head1, Node head2) {

        Node mergedLL = new Node(-1);

        Node temp = mergedLL;

        while(head1 != null && head2 != null) {

            if(head1.data <= head2.data) {

                temp.next = head1;

                head1 = head1.next;

                temp = temp.next;

            } else {

                temp.next = head2;

                head2 = head2.next;

                temp = temp.next;

            }

        }

        while(head1 != null) {

            temp.next = head1;

            head1 = head1.next;

            temp = temp.next;

        }

        while(head2 != null) {

            temp.next = head2;

            head2 = head2.next;

            temp = temp.next;

        }

        return mergedLL.next;

    }

    public Node mergeSort(Node head) {

        // base case

        if(head == null || head.next == null) {

            return head;

        }

        // find mid

        Node mid = getMid(head);

       

        Node rightHead = mid.next;

        mid.next = null;

        Node newLeft = mergeSort(head);

        Node newRight = mergeSort(rightHead);

       

        // merge

        return merge(newLeft, newRight);

    }

}

public class Main {

    public static void main(String[] args) {

        LinkedList ll = new LinkedList();

        ll.addFirst(1);

        ll.addFirst(2);

        ll.addFirst(3);

        ll.addFirst(4);

        ll.addFirst(5);

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

        System.out.println("Original List:");

        ll.printList();

        ll.head = ll.mergeSort(ll.head);

        System.out.println("Sorted List:");

        ll.printList();

    }

}

LinkedList - JCF

 import java.util.LinkedList;

public class Main {

    public static void main(String[] args) {

       

       LinkedList<Integer> ll = new LinkedList<>();

       

       // add

       ll.addLast(1);

       ll.addLast(2);

       ll.addFirst(0);

       

       // LinkedList after insertion

       // (head -> 0 -> 1 -> 2)

       System.out.println(ll);

       

       // remove

       ll.removeLast();

       ll.removeFirst();

       System.out.println(ll);

    }

} OUTPUT: 0->1->2

// after remove = 1

Backup - code LinkedList

 public class Main {

    // Node class remains the same

    class Node {

        int data;

        Node next;

        Node(int data) {

            this.data = data;

            this.next = null;

        }

    }

    // 1. Declare head and tail as member variables for the list

    Node head;

    Node tail;

    int size = 0; // Keep track of the size

    // 2. Implement the 'add' methods for your custom list

    public void addFirst(int data) {

        Node newNode = new Node(data);

        size++;

        if (head == null) {

            head = tail = newNode;

            return;

        }

        newNode.next = head;

        head = newNode;

    }

    public void addLast(int data) {

        Node newNode = new Node(data);

        size++;

        if (head == null) {

            head = tail = newNode;

            return;

        }

        tail.next = newNode;

        tail = newNode;

    }

    public void add(int index, int data) {

        if (index < 0 || index > size) {

            System.out.println("Invalid index");

            return;

        }

        if (index == 0) {

            addFirst(data);

            return;

        }

        Node temp = head;

        for (int i = 0; i < index - 1; i++) {

            temp = temp.next;

        }

        Node newNode = new Node(data);

        newNode.next = temp.next;

        temp.next = newNode;

        size++;

    }

    public void deleteNthfromEnd(int n) {

        // calculate size

        int size = 0;

        Node temp = head;

        while(temp != null) {

            temp = temp.next;

            size++;

        }

        if(n == size) {

            head = head.next; // removeFirst

            return;

        }

        // size-n

        int i = 1;

        int iToFind = size-n;

        Node prev = head;

        while(i < iToFind) {

            prev = prev.next;

            i++;

        }

        prev.next = prev.next.next;

        return;

    }

    // Your reverse method is correct for this custom implementation

    public void reverse() {

        Node prev = null;

        Node curr = tail = head; // The old head becomes the new tail

        Node next;

        while (curr != null) {

            next = curr.next; // Store the next node

            curr.next = prev; // Reverse the current node's pointer

            prev = curr;      // Move pointers one position ahead

            curr = next;      // Move pointers one position ahead

        }

        head = prev; // The last node visited (prev) is the new head

    }

    // Your printList method is correct for this custom implementation

    public void printList() {

        Node temp = head;

        while (temp != null) {

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

            temp = temp.next;

        }

        System.out.println("null");

    }

    public static void main(String[] args) {

        // 3. Instantiate your custom Main class, not java.util.LinkedList

        Main ll = new Main();

       

        // The list will be: 2 -> 2 -> 4 -> 5

        ll.addFirst(2);

        ll.addFirst(1);

        ll.addLast(4);

        ll.addLast(5);

        // After this, the list is: 2 -> 2 -> 3 -> 4 -> 5

        ll.add(2, 3);

        System.out.println("Original List:");

        ll.printList();

        ll.deleteNthfromEnd(3);

        ll.printList();

    }

}

Java Collections Frameworks - They are all Optimized already!?

 import java.util.LinkedList;  // Java Collections Framework - optimized with best T.C

class Main {

    public static void main(String[] args) {

        // create -

        LinkedList<Integer> ll = new LinkedList<>();

        // add

        ll.addLast(1);

        ll.addLast(2);

        ll.addFirst(0);

        //0->1->2

        System.out.println(ll);

        // remove

        ll.removeLast();

        ll.removeFirst();

        System.out.println(ll);

       

    }

}

Remove Cycle in LL using Java

 class Node {

    int data;

    Node next;

    Node(int data) {

        this.data = data;

        this.next = null;

    }

}

class LinkedList {

    Node head;

    public void add(int data) {

        Node newNode = new Node(data);

        if (head == null) {

            head = newNode;

            return;

        }

        Node temp = head;

        while (temp.next != null) {

            temp = temp.next;

        }

        temp.next = newNode;

    }

    public void printList() {

        Node temp = head;

        while (temp != null) {

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

            temp = temp.next;

        }

        System.out.println();

    }

    // ✅ cycle detection

    public boolean isCycle() {

        Node slow = head;

        Node fast = head;

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

            slow = slow.next;

            fast = fast.next.next;

            if (slow == fast) {

                return true; // cycle exists

            }

        }

        return false;

    }

    // ✅ cycle removal

    public void removeCycle() {

        Node slow = head;

        Node fast = head;

        boolean cycle = false;

        // Step 1: Detect cycle

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

            slow = slow.next;

            fast = fast.next.next;

            if (fast == slow) {

                cycle = true;

                break;

            }

        }

        if (!cycle) return; // no cycle found

        // Step 2: Move slow back to head

        slow = head;

        Node prev = null;

        // Step 3: Find meeting point

        while (slow != fast) {

            prev = fast;     // track last node

            slow = slow.next;

            fast = fast.next;

        }

        // Step 4: Break the cycle

        prev.next = null;

    }

}

public class Main {

    public static void main(String[] args) {

        LinkedList list = new LinkedList();

        // creating a cycle manually: 1 -> 2 -> 3 -> back to 2

        list.head = new Node(1);

        list.head.next = new Node(2);

        list.head.next.next = new Node(3);

        list.head.next.next.next = list.head.next; // cycle

        System.out.println("Has cycle? " + list.isCycle()); // true ✅

        list.removeCycle();

        System.out.println("Has cycle? " + list.isCycle()); // false ✅

        // Now safe to print

        list.printList(); // 1 2 3

    }

}

Check if LL is a palindrome (Java)

 class Node {

    int data;

    Node next;

    Node(int data) {

        this.data = data;

        this.next = null;

    }

}

class LinkedList {

    Node head;

    public void add(int data) {

        Node newNode = new Node(data);

        if (head == null) {

            head = newNode;

            return;

        }

        Node temp = head;

        while (temp.next != null) {

            temp = temp.next;

        }

        temp.next = newNode;

    }

    public void printList() {

        Node temp = head;

        while (temp != null) {

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

            temp = temp.next;

        }

        System.out.println();

    }

    // helper function to find middle

    public Node findMid(Node head) {

        Node slow = head;

        Node fast = head;

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

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

    // check if linked list is palindrome

    public boolean checkPalindrome() {

        if (head == null || head.next == null) {

            return true;

        }

        // step1: find mid

        Node midNode = findMid(head);

        // step2: reverse 2nd half

        Node prev = null;

        Node curr = midNode;

        Node next;

        while (curr != null) {

            next = curr.next;

            curr.next = prev;

            prev = curr;

            curr = next;

        }

        Node right = prev; // head of reversed half

        Node left = head;

        // step3: check both halves

        while (right != null) {

            if (left.data != right.data) {

                return false;

            }

            left = left.next;

            right = right.next;

        }

        return true;

    }

}

public class Main {

    public static void main(String[] args) {

        LinkedList ll = new LinkedList();

        ll.add(1);

        ll.add(2);

        ll.add(1);

        // ll.add(1);

        ll.printList();  // ✅ print list

        System.out.println(ll.checkPalindrome()); // ✅ true

    }

}