4142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
import.java.util.*;
// Node definition for singly-linked list
class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

class Solution {

    // Function to segregate even and odd nodes in a linked list
    public Node segregateEvenOdd(Node head) {

        // Edge case: If list is empty or has only one node
        if (head == null || head.next == null) return head;

        // Create pointers for the heads and tails of even and odd lists
        Node evenHead = null, evenTail = null;
        Node oddHead = null, oddTail = null;

        // Pointer to traverse the list
        Node current = head;

        // Traverse the linked list
        while (current != null) {

            // If the current node has even value
            if (current.data % 2 == 0) {

                // First even node
                if (evenHead == null) {
                    evenHead = current;
                    evenTail = current;
                } else {
                    evenTail.next = current;
                    evenTail = current;
                }

            } else {
                // If the current node has odd value

                // First odd node
                if (oddHead == null) {
                    oddHead = current;
                    oddTail = current;
                } else {
                    oddTail.next = current;
                    oddTail = current;
                }
            }

            // Move to next node
            current = current.next;
        }

        // If no even nodes found, return odd list
        if (evenHead == null) return oddHead;

        // If no odd nodes found, return even list
        if (oddHead == null) return evenHead;

        // Combine even and odd lists
        evenTail.next = oddHead;

        // Set end of list to null
        oddTail.next = null;

        return evenHead;
    }
}

// Driver code
class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();

        // Creating linked list: 17 -> 15 -> 8 -> 12 -> 10 -> 5 -> 4
        Node head = new Node(17);
        head.next = new Node(15);
        head.next.next = new Node(8);
        head.next.next.next = new Node(12);
        head.next.next.next.next = new Node(10);
        head.next.next.next.next.next = new Node(5);
        head.next.next.next.next.next.next = new Node(4);

        // Call segregation function
        Node newHead = sol.segregateEvenOdd(head);

        // Print result
        while (newHead != null) {
            System.out.print(newHead.data + " ");
            newHead = newHead.next;
        }
    }
}
123456789101112131415161718192021222324