List 4: 8 Merged Linked List: 1 1 1 2 3 4 5 6 7 8

import java.util.*;

// Node class represents a node in a linked list
class Node {
    // Data stored in the node
    int data;

    // Pointer to the next node in the list
    Node next;

    // Constructor with both data and next node as parameters
    Node(int data1, Node next1) {
        data = data1;
        next = next1;
    }

    // Constructor with only data as a parameter, sets next to null
    Node(int data1) {
        data = data1;
        next = null;
    }
}

public class Main {
    // Function to convert an ArrayList to a linked list
    static Node convertArrToLinkedList(ArrayList<Integer> arr) {
        // Create a dummy node to serve as the head of the linked list
        Node dummyNode = new Node(-1, null);
        Node temp = dummyNode;

        // Iterate through the ArrayList and create nodes with elements
        for (int i = 0; i < arr.size(); i++) {
            // Create a new node with the ArrayList element
            temp.next = new Node(arr.get(i), null);
            // Move the temporary pointer to the newly created node
            temp = temp.next;
        }

        // Return the linked list starting from the next of the dummy node
        return dummyNode.next;
    }

    // Function to merge K sorted linked lists
    static Node mergeKLists(ArrayList<Node> listArray) {
        // Create an ArrayList to store node values
        ArrayList<Integer> arr = new ArrayList<>();

        // Iterate through the listArray containing all linked lists
        for (int i = 0; i < listArray.size(); i++) {
            // Initialize a temporary pointer to the head of the current linked list
            Node temp = listArray.get(i);

            // Traverse through the current linked list
            while (temp != null) {
                // Store the data of each node in the ArrayList
                arr.add(temp.data);

                // Move to the next node in the linked list
                temp = temp.next;
            }
        }

        // Sort the ArrayList containing node values in ascending order
        Collections.sort(arr);

        // Convert the sorted ArrayList back to a linked list and return its head
        return convertArrToLinkedList(arr);
    }

    // Function to print the linked list
    static void printLinkedList(Node head) {
        Node temp = head;
        while (temp != null) {
            // Print the data of the current node
            System.out.print(temp.data + " ");
            // Move to the next node
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create linked lists
        Node head1 = new Node(2, new Node(4, new Node(6)));
        Node head2 = new Node(1, new Node(5));
        Node head3 = new Node(1, new Node(1, new Node(3, new Node(7))));
        Node head4 = new Node(8);

        // Populate the lists ArrayList
        ArrayList<Node> lists = new ArrayList<>();
        lists.add(head1);
        lists.add(head2);
        lists.add(head3);
        lists.add(head4);

        System.out.println("Original Linked Lists:");
        for (int i = 0; i < lists.size(); ++i) {
            System.out.print("List " + (i + 1) + ": ");
            printLinkedList(lists.get(i));
        }

        // Merge the linked lists
        Node mergedList = mergeKLists(lists);

        // Print the merged linked list
        System.out.print("Merged Linked List: ");
        printLinkedList(mergedList);
    }
}
Original Linked Lists: List