Given a Linked List. The Linked List is in alternating ascending and descending orders. Sort the list efficiently.
Example:
Input List: 10 -> 40 -> 53 -> 30 -> 67 -> 12 -> 89 -> NULL Output List: 10 -> 12 -> 30 -> 40 -> 53 -> 67 -> 89 -> NULL Input List: 1 -> 4 -> 3 -> 2 -> 5 -> NULL Output List: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Simple Solution:
Approach: The basic idea is to apply to merge sort on the linked list.
The implementation is discussed in this article: Merge Sort for linked List.
Complexity Analysis:
- Time Complexity: The merge sort of linked list takes O(n log n) time. In the merge sort tree, the height is log n. Sorting each level will take O(n) time. So time complexity is O(n log n).
- Auxiliary Space: O(n log n), In the merge sort tree the height is log n. Storing each level will take O(n) space. So space complexity is O(n log n).
Efficient Solution:
Approach:
- Separate two lists.
- Reverse the one with descending order
- Merge both lists.
Diagram:
Below are the implementations of the above algorithm:
Javascript
<script>// Javascript program to sort a// linked list that is alternatively// sorted in increasing and decreasing order// head of listvar head; // Linked list Node class Node { constructor(val) { this.data = val; this.next = null; }}function newNode(key) { return new Node(key);}/* This is the main function that sorts the linked list. */function sort() { /* Create 2 dummy nodes and initialise as heads of linked lists */ var Ahead = new Node(0), Dhead = new Node(0); // Split the list into lists splitList(Ahead, Dhead); Ahead = Ahead.next; Dhead = Dhead.next; // Reverse the descending list Dhead = reverseList(Dhead); // Merge the 2 linked lists head = mergeList(Ahead, Dhead);}// Function to reverse the linked list function reverseList(Dhead) { var current = Dhead; var prev = null; var next; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } Dhead = prev; return Dhead;}// Function to print linked list function printList() { var temp = head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } document.write();}// A utility function to merge// two sorted linked listsfunction mergeList(head1, head2) { // Base cases if (head1 == null) return head2; if (head2 == null) return head1; var temp = null; if (head1.data < head2.data) { temp = head1; head1.next = mergeList(head1.next, head2); } else { temp = head2; head2.next = mergeList(head1, head2.next); } return temp;}// This function alternatively splits// a linked list with head as head into two:// For example, 10->20->30->15->40->7 is// splitted into 10->30->40 and 20->15->7// "Ahead" is reference to head of ascending // linked list// "Dhead" is reference to head of descending // linked listfunction splitList(Ahead, Dhead) { var ascn = Ahead; var dscn = Dhead; var curr = head; // Link alternate nodes while (curr != null) { // Link alternate nodes in // ascending order ascn.next = curr; ascn = ascn.next; curr = curr.next; if (curr != null) { dscn.next = curr; dscn = dscn.next; curr = curr.next; } } ascn.next = null; dscn.next = null;}// Driver code head = newNode(10);head.next = newNode(40);head.next.next = newNode(53);head.next.next.next = newNode(30);head.next.next.next.next = newNode(67);head.next.next.next.next.next = newNode(12);head.next.next.next.next.next.next = newNode(89);document.write("Given linked list<br/>");printList();sort();document.write("<br/>Sorted linked list<br/>");printList();// This code contributed by aashish1995 </script> |
Output:
Given Linked List is 10 40 53 30 67 12 89 Sorted Linked List is 10 12 30 40 53 67 89
Complexity Analysis:
- Time Complexity: O(n).
One traversal is needed to separate the list and reverse them. The merging of sorted lists takes O(n) time. - Auxiliary Space: O(1).
No extra space is required.
Please refer complete article on Sort a linked list that is sorted alternating ascending and descending orders? for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
