Javascript Program For Sorting A Linked List That Is Sorted Alternating Ascending And Descending Orders

Last Updated : 05 Sep, 2024

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

// Javascript program to sort a
// linked list that is alternatively
// sorted in increasing and decreasing order

// head of list
let 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 */
    let 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) {
    let current = Dhead;
    let prev = null;
    let 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() {
    let temp = head;
    while (temp != null) {
        console.log(temp.data + " ");
        temp = temp.next;
    }
    console.log();
}

// A utility function to merge
// two sorted linked lists
function mergeList(head1, head2) {
    // Base cases
    if (head1 == null)
        return head2;
    if (head2 == null)
        return head1;

    let 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 list
function splitList(Ahead, Dhead) {
    let ascn = Ahead;
    let dscn = Dhead;
    let 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);
console.log("Given linked list");
printList();

sort();

console.log("Sorted linked list");
printList();
// This code contributed by aashish1995

Output

Given linked list
10 
40 
53 
30 
67 
12 
89 

Sorted linked list
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!