Untitled
unknown
plain_text
23 days ago
3.5 kB
2
Indexable
Never
class DoublyLinkedList { class Node { int data; Node prev; Node next; Node(int data) { this.data = data; this.prev = null; this.next = null; } } Node head, tail; DoublyLinkedList() { head = null; tail = null; } // Function to add a new node at the end of the list void addNode(int data) { Node newNode = new Node(data); if (head == null) { head = newNode; tail = newNode; } else { tail.next = newNode; newNode.prev = tail; tail = newNode; } } // Function to split the doubly linked list into two halves Node split(Node head) { Node slow = head; Node fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } Node secondHalf = slow.next; slow.next = null; if (secondHalf != null) { secondHalf.prev = null; } return secondHalf; } // Function to merge two sorted halves Node merge(Node first, Node second) { if (first == null) return second; if (second == null) return first; if (first.data <= second.data) { first.next = merge(first.next, second); first.next.prev = first; first.prev = null; return first; } else { second.next = merge(first, second.next); second.next.prev = second; second.prev = null; return second; } } // Merge sort function for doubly linked list Node mergeSort(Node head) { if (head == null || head.next == null) { return head; } Node secondHalf = split(head); head = mergeSort(head); secondHalf = mergeSort(secondHalf); return merge(head, secondHalf); } // Function to print the list from head to tail void printList() { Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } // Function to print the list from tail to head void printListReverse() { Node current = tail; while (current != null) { System.out.print(current.data + " "); current = current.prev; } System.out.println(); } // Function to sort the list void sort() { if (head != null) { head = mergeSort(head); // Update tail pointer Node current = head; while (current.next != null) { current = current.next; } tail = current; } } public static void main(String[] args) { java.util.Scanner sc = new java.util.Scanner(System.in); int n = sc.nextInt(); DoublyLinkedList dll = new DoublyLinkedList(); for (int i = 0; i < n; i++) { dll.addNode(sc.nextInt()); } // Sort the list dll.sort(); // Print the sorted list dll.printList(); // Print the reverse sorted list dll.printListReverse(); sc.close(); } }
Leave a Comment