Sort a linked list that is sorted alternating ascending and descending orders

The alternately linked list includes the ascending and descending order nodes in the alternate position. Our goal is to sort the linked list in an efficient way. So that all the elements come in ascending order. For example.

Example 1
----------
    List    7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    Alternating ascending order
            7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
            ↑         ↑         ↑         ↑       ↑
    Alternating descending order
            7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
                ↑         ↑         ↑         ↑      
    Sorted list
            7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
Example 2
---------
    List    1 → 10 → 2 → 9 → 3 → 8 → 4 → 7 → NULL
    Alternating ascending order
            1 → 10 → 2 → 9 → 3 → 8 → 4 → 7 → NULL
            ↑        ↑       ↑       ↑       
    Alternating descending order
            1 → 10 → 2 → 9 → 3 → 8 → 4 → 7 → NULL
                ↑        ↑       ↑       ↑       
    Sorted list
            1 → 2 → 3 → 4 → 7 → 8 → 9 → 10 → NULL

Here given code implementation process.

/*
    C program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
#include <stdio.h>
#include <stdlib.h>

// Linked List LinkNode
struct LinkNode
{
    int data;
    struct LinkNode *next;
};
// Singly linked list 
struct SingleLL
{
    struct LinkNode *head;
    struct LinkNode *tail;
};
// Returns the new linked list
struct SingleLL *newLinkedList()
{
    // Create memory of head and tail Nodes
    struct SingleLL *sll = (struct SingleLL *) 
        malloc(sizeof(struct SingleLL));
    if (sll == NULL)
    {
        printf("Memory overflow\n");
    }
    else
    {
        sll->head = NULL;
        sll->tail = NULL;
    }
    return sll;
}
// Handles the request of adding new node in linked list
void addNode(struct SingleLL *sll, int data)
{
    // Create dynamic node
    struct LinkNode *node = (struct LinkNode *) 
        malloc(sizeof(struct LinkNode));
    if (node == NULL)
    {
        printf("Memory overflow to Create LinkNode\n");
        return;
    }
    else
    {
        // Set initial node value
        node->data = data;
        node->next = NULL;
    }
    if (sll->head == NULL)
    {
        sll->head = node;
    }
    else
    {
        sll->tail->next = node;
    }
    sll->tail = node;
}
// Display linked list element
void display(struct LinkNode *node)
{
    if (node == NULL)
    {
        return;
    }
    struct LinkNode *temp = node;
    // iterating linked list elements
    while (temp != NULL)
    {
        printf(" %d →", temp->data);
        // Visit to next node
        temp = temp->next;
    }
    printf(" NULL\n");
}
void sort(struct SingleLL *sll)
{
    if (sll->head == NULL || sll->head->next == NULL)
    {
        // less than 2 nodes
        return;
    }
    // Auxiliary variables
    struct LinkNode *first = NULL;
    struct LinkNode *second = NULL;
    struct LinkNode *point = NULL;
    struct LinkNode *temp = sll->head;
    struct LinkNode *auxiliary = NULL;
    int count = 0;
    // Split the linked list nodes
    while (temp != NULL)
    {
        if (count % 2 == 0)
        {
            // Add node in first list 
            // Add node at the end of linked list
            if (first == NULL)
            {
                first = temp;
                point = temp;
            }
            else
            {
                point->next = temp;
                point = temp;
            }
            // Visit to next node
            temp = temp->next;
            // no next node
            point->next = NULL;
        }
        else
        {
            // Add node at beginning of second linked list
            // Collect new node
            auxiliary = temp;
            // Visit to next node
            temp = temp->next;
            // Connect current node to previous head of second list
            auxiliary->next = second;
            // Set first node of second list
            second = auxiliary;
        }
        count++;
    }
    auxiliary = NULL;
    // Combine alternating nodes in sorted order
    while (count > 0)
    {
        if (first != NULL && second != NULL)
        {
            if (first->data < second->data)
            {
                if (auxiliary == NULL)
                {
                    // First node of resultant linked list
                    sll->head = first;
                    auxiliary = first;
                    sll->tail = first;
                }
                else
                {
                    auxiliary->next = first;
                    sll->tail = first;
                }
                auxiliary = first;
                // Visit to next node
                first = first->next;
            }
            else
            {
                if (auxiliary == NULL)
                {
                    // First node of resultant linked list
                    sll->head = second;
                    auxiliary = second;
                }
                else
                {
                    auxiliary->next = second;
                }
                auxiliary = second;
                // Visit to next node
                second = second->next;
            }
        }
        else if (first != NULL)
        {
            // When element exists in first linked list
            auxiliary->next = first;
            // new last node
            auxiliary = first;
            // Visit to next node
            first = first->next;
        }
        else
        {
            // When element exists in second linked list
            auxiliary->next = second;
            // new last node
            auxiliary = second;
            // Visit to next node
            second = second->next;
        }
        // Set new last node
        sll->tail = auxiliary;
        count--;
    }
}
int main(int argc, char
    const *argv[])
{
    struct SingleLL *sll = newLinkedList();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    addNode(sll, 7);
    addNode(sll, 45);
    addNode(sll, 15);
    addNode(sll, 18);
    addNode(sll, 40);
    addNode(sll, 12);
    addNode(sll, 60);
    addNode(sll, 9);
    addNode(sll, 80);
    printf(" Before Sort :");
    display(sll->head);
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    // Alternating ascending order
    // 7 → 15 → 40 → 60 → 80 → NULL
    // Alternating descending order
    // 45 → 18 → 12 → 9 → NULL
    // Result
    // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    sort(sll);
    printf(" After Sort :");
    display(sll->head);
    return 0;
}
Sort linked list

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
/*
    Java program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public LinkNode tail;
    public SingleLL()
    {
        this.head = null;
        this.tail = null;
    }
    // Add new Node at end of linked list 
    public void addNode(int data)
    {
        LinkNode node = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            System.out.print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        System.out.print(" NULL\n");
    }
    public void sort()
    {
        if (this.head == null || this.head.next == null)
        {
            // less than 2 nodes
            return;
        }
        // Auxiliary variables
        LinkNode first = null;
        LinkNode second = null;
        LinkNode point = null;
        LinkNode temp = this.head;
        LinkNode auxiliary = null;
        int count = 0;
        // Split the linked list nodes
        while (temp != null)
        {
            if (count % 2 == 0)
            {
                // Add node in first list 
                // Add node at the end of linked list
                if (first == null)
                {
                    first = temp;
                    point = temp;
                }
                else
                {
                    point.next = temp;
                    point = temp;
                }
                // Visit to next node
                temp = temp.next;
                // no next node
                point.next = null;
            }
            else
            {
                // Add node at beginning of second linked list
                // Collect new node
                auxiliary = temp;
                // Visit to next node
                temp = temp.next;
                // Connect current node to previous head of second list
                auxiliary.next = second;
                // Set first node of second list
                second = auxiliary;
            }
            count++;
        }
        auxiliary = null;
        // Combine alternating nodes in sorted order
        while (count > 0)
        {
            if (first != null && second != null)
            {
                if (first.data < second.data)
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = first;
                        auxiliary = first;
                    }
                    else
                    {
                        auxiliary.next = first;
                    }
                    auxiliary = first;
                    // Visit to next node
                    first = first.next;
                }
                else
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = second;
                        auxiliary = second;
                    }
                    else
                    {
                        auxiliary.next = second;
                    }
                    auxiliary = second;
                    // Visit to next node
                    second = second.next;
                }
            }
            else if (first != null)
            {
                // When element exists in first linked list
                auxiliary.next = first;
                // new last node
                auxiliary = first;
                // Visit to next node
                first = first.next;
            }
            else
            {
                // When element exists in second linked list
                auxiliary.next = second;
                // new last node
                auxiliary = second;
                // Visit to next node
                second = second.next;
            }
            // Set new last node
            this.tail = auxiliary;
            count--;
        }
    }
    public static void main(String[] args)
    {
        SingleLL sll = new SingleLL();
        // Linked list
        // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
        sll.addNode(7);
        sll.addNode(45);
        sll.addNode(15);
        sll.addNode(18);
        sll.addNode(40);
        sll.addNode(12);
        sll.addNode(60);
        sll.addNode(9);
        sll.addNode(80);
        System.out.print(" Before Sort :");
        sll.display();
        // Linked list
        // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
        // Alternating ascending order
        // 7 → 15 → 40 → 60 → 80 → NULL
        // Alternating descending order
        // 45 → 18 → 12 → 9 → NULL
        // Result
        // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
        sll.sort();
        System.out.print(" After Sort :");
        sll.display();
    }
}

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
// Include header file
#include <iostream>
using namespace std;
/*
    C++ program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
class LinkNode
{
    public: int data;
    LinkNode *next;
    LinkNode(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
class SingleLL
{
    public: LinkNode *head;
    LinkNode *tail;
    SingleLL()
    {
        this->head = NULL;
        this->tail = NULL;
    }
    // Add new Node at end of linked list 
    void addNode(int data)
    {
        LinkNode *node = new LinkNode(data);
        if (this->head == NULL)
        {
            this->head = node;
        }
        else
        {
            // Append the node at last position
            this->tail->next = node;
        }
        this->tail = node;
    }
    // Display linked list element
    void display()
    {
        if (this->head == NULL)
        {
            return;
        }
        LinkNode *temp = this->head;
        // iterating linked list elements
        while (temp != NULL)
        {
            cout << " " << temp->data << " →";
            // Visit to next node
            temp = temp->next;
        }
        cout << " NULL\n";
    }
    void sort()
    {
        if (this->head == NULL || this->head->next == NULL)
        {
            // less than 2 nodes
            return;
        }
        // Auxiliary variables
        LinkNode *first = NULL;
        LinkNode *second = NULL;
        LinkNode *point = NULL;
        LinkNode *temp = this->head;
        LinkNode *auxiliary = NULL;
        int count = 0;
        // Split the linked list nodes
        while (temp != NULL)
        {
            if (count % 2 == 0)
            {
                // Add node in first list 
                // Add node at the end of linked list
                if (first == NULL)
                {
                    first = temp;
                    point = temp;
                }
                else
                {
                    point->next = temp;
                    point = temp;
                }
                // Visit to next node
                temp = temp->next;
                // no next node
                point->next = NULL;
            }
            else
            {
                // Add node at beginning of second linked list
                // Collect new node
                auxiliary = temp;
                // Visit to next node
                temp = temp->next;
                // Connect current node to previous head of second list
                auxiliary->next = second;
                // Set first node of second list
                second = auxiliary;
            }
            count++;
        }
        auxiliary = NULL;
        // Combine alternating nodes in sorted order
        while (count > 0)
        {
            if (first != NULL && second != NULL)
            {
                if (first->data < second->data)
                {
                    if (auxiliary == NULL)
                    {
                        // First node of resultant linked list
                        this->head = first;
                        auxiliary = first;
                    }
                    else
                    {
                        auxiliary->next = first;
                    }
                    auxiliary = first;
                    // Visit to next node
                    first = first->next;
                }
                else
                {
                    if (auxiliary == NULL)
                    {
                        // First node of resultant linked list
                        this->head = second;
                        auxiliary = second;
                    }
                    else
                    {
                        auxiliary->next = second;
                    }
                    auxiliary = second;
                    // Visit to next node
                    second = second->next;
                }
            }
            else if (first != NULL)
            {
                // When element exists in first linked list
                auxiliary->next = first;
                // new last node
                auxiliary = first;
                // Visit to next node
                first = first->next;
            }
            else
            {
                // When element exists in second linked list
                auxiliary->next = second;
                // new last node
                auxiliary = second;
                // Visit to next node
                second = second->next;
            }
            // Set new last node
            this->tail = auxiliary;
            count--;
        }
    }
};
int main()
{
    SingleLL *sll = new SingleLL();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    sll->addNode(7);
    sll->addNode(45);
    sll->addNode(15);
    sll->addNode(18);
    sll->addNode(40);
    sll->addNode(12);
    sll->addNode(60);
    sll->addNode(9);
    sll->addNode(80);
    cout << " Before Sort :";
    sll->display();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    // Alternating ascending order
    // 7 → 15 → 40 → 60 → 80 → NULL
    // Alternating descending order
    // 45 → 18 → 12 → 9 → NULL
    // Result
    // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    sll->sort();
    cout << " After Sort :";
    sll->display();
    return 0;
}

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
// Include namespace system
using System;
/*
    Csharp program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
public class LinkNode
{
    public int data;
    public LinkNode next;
    public LinkNode(int data)
    {
        this.data = data;
        this.next = null;
    }
}
public class SingleLL
{
    public LinkNode head;
    public LinkNode tail;
    public SingleLL()
    {
        this.head = null;
        this.tail = null;
    }
    // Add new Node at end of linked list 
    public void addNode(int data)
    {
        LinkNode node = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    public void display()
    {
        if (this.head == null)
        {
            return;
        }
        LinkNode temp = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            Console.Write(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        Console.Write(" NULL\n");
    }
    public void sort()
    {
        if (this.head == null || this.head.next == null)
        {
            // less than 2 nodes
            return;
        }
        // Auxiliary variables
        LinkNode first = null;
        LinkNode second = null;
        LinkNode point = null;
        LinkNode temp = this.head;
        LinkNode auxiliary = null;
        int count = 0;
        // Split the linked list nodes
        while (temp != null)
        {
            if (count % 2 == 0)
            {
                // Add node in first list 
                // Add node at the end of linked list
                if (first == null)
                {
                    first = temp;
                    point = temp;
                }
                else
                {
                    point.next = temp;
                    point = temp;
                }
                // Visit to next node
                temp = temp.next;
                // no next node
                point.next = null;
            }
            else
            {
                // Add node at beginning of second linked list
                // Collect new node
                auxiliary = temp;
                // Visit to next node
                temp = temp.next;
                // Connect current node to previous head of second list
                auxiliary.next = second;
                // Set first node of second list
                second = auxiliary;
            }
            count++;
        }
        auxiliary = null;
        // Combine alternating nodes in sorted order
        while (count > 0)
        {
            if (first != null && second != null)
            {
                if (first.data < second.data)
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = first;
                        auxiliary = first;
                    }
                    else
                    {
                        auxiliary.next = first;
                    }
                    auxiliary = first;
                    // Visit to next node
                    first = first.next;
                }
                else
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = second;
                        auxiliary = second;
                    }
                    else
                    {
                        auxiliary.next = second;
                    }
                    auxiliary = second;
                    // Visit to next node
                    second = second.next;
                }
            }
            else if (first != null)
            {
                // When element exists in first linked list
                auxiliary.next = first;
                // new last node
                auxiliary = first;
                // Visit to next node
                first = first.next;
            }
            else
            {
                // When element exists in second linked list
                auxiliary.next = second;
                // new last node
                auxiliary = second;
                // Visit to next node
                second = second.next;
            }
            // Set new last node
            this.tail = auxiliary;
            count--;
        }
    }
    public static void Main(String[] args)
    {
        SingleLL sll = new SingleLL();
        // Linked list
        // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
        sll.addNode(7);
        sll.addNode(45);
        sll.addNode(15);
        sll.addNode(18);
        sll.addNode(40);
        sll.addNode(12);
        sll.addNode(60);
        sll.addNode(9);
        sll.addNode(80);
        Console.Write(" Before Sort :");
        sll.display();
        // Linked list
        // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
        // Alternating ascending order
        // 7 → 15 → 40 → 60 → 80 → NULL
        // Alternating descending order
        // 45 → 18 → 12 → 9 → NULL
        // Result
        // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
        sll.sort();
        Console.Write(" After Sort :");
        sll.display();
    }
}

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
<?php
/*
    Php program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
class LinkNode
{
    public $data;
    public $next;
    public  function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }
}
class SingleLL
{
    public $head;
    public $tail;
    public  function __construct()
    {
        $this->head = NULL;
        $this->tail = NULL;
    }
    // Add new Node at end of linked list 
    public  function addNode($data)
    {
        $node = new LinkNode($data);
        if ($this->head == NULL)
        {
            $this->head = $node;
        }
        else
        {
            // Append the node at last position
            $this->tail->next = $node;
        }
        $this->tail = $node;
    }
    // Display linked list element
    public  function display()
    {
        if ($this->head == NULL)
        {
            return;
        }
        $temp = $this->head;
        // iterating linked list elements
        while ($temp != NULL)
        {
            echo(" ".$temp->data.
                " →");
            // Visit to next node
            $temp = $temp->next;
        }
        echo(" NULL\n");
    }
    public  function sort()
    {
        if ($this->head == NULL || $this->head->next == NULL)
        {
            // less than 2 nodes
            return;
        }
        // Auxiliary variables
        $first = NULL;
        $second = NULL;
        $point = NULL;
        $temp = $this->head;
        $auxiliary = NULL;
        $count = 0;
        // Split the linked list nodes
        while ($temp != NULL)
        {
            if ($count % 2 == 0)
            {
                // Add node in first list 
                // Add node at the end of linked list
                if ($first == NULL)
                {
                    $first = $temp;
                    $point = $temp;
                }
                else
                {
                    $point->next = $temp;
                    $point = $temp;
                }
                // Visit to next node
                $temp = $temp->next;
                // no next node
                $point->next = NULL;
            }
            else
            {
                // Add node at beginning of second linked list
                // Collect new node
                $auxiliary = $temp;
                // Visit to next node
                $temp = $temp->next;
                // Connect current node to previous head of second list
                $auxiliary->next = $second;
                // Set first node of second list
                $second = $auxiliary;
            }
            $count++;
        }
        $auxiliary = NULL;
        // Combine alternating nodes in sorted order
        while ($count > 0)
        {
            if ($first != NULL && $second != NULL)
            {
                if ($first->data < $second->data)
                {
                    if ($auxiliary == NULL)
                    {
                        // First node of resultant linked list
                        $this->head = $first;
                        $auxiliary = $first;
                    }
                    else
                    {
                        $auxiliary->next = $first;
                    }
                    $auxiliary = $first;
                    // Visit to next node
                    $first = $first->next;
                }
                else
                {
                    if ($auxiliary == NULL)
                    {
                        // First node of resultant linked list
                        $this->head = $second;
                        $auxiliary = $second;
                    }
                    else
                    {
                        $auxiliary->next = $second;
                    }
                    $auxiliary = $second;
                    // Visit to next node
                    $second = $second->next;
                }
            }
            else if ($first != NULL)
            {
                // When element exists in first linked list
                $auxiliary->next = $first;
                // new last node
                $auxiliary = $first;
                // Visit to next node
                $first = $first->next;
            }
            else
            {
                // When element exists in second linked list
                $auxiliary->next = $second;
                // new last node
                $auxiliary = $second;
                // Visit to next node
                $second = $second->next;
            }
            // Set new last node
            $this->tail = $auxiliary;
            $count--;
        }
    }
}

function main()
{
    $sll = new SingleLL();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    $sll->addNode(7);
    $sll->addNode(45);
    $sll->addNode(15);
    $sll->addNode(18);
    $sll->addNode(40);
    $sll->addNode(12);
    $sll->addNode(60);
    $sll->addNode(9);
    $sll->addNode(80);
    echo(" Before Sort :");
    $sll->display();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    // Alternating ascending order
    // 7 → 15 → 40 → 60 → 80 → NULL
    // Alternating descending order
    // 45 → 18 → 12 → 9 → NULL
    // Result
    // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    $sll->sort();
    echo(" After Sort :");
    $sll->display();
}
main();

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
/*
    Node JS program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
class LinkNode
{
    constructor(data)
    {
        this.data = data;
        this.next = null;
    }
}
class SingleLL
{
    constructor()
    {
        this.head = null;
        this.tail = null;
    }
    // Add new Node at end of linked list 
    addNode(data)
    {
        var node = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    display()
    {
        if (this.head == null)
        {
            return;
        }
        var temp = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            process.stdout.write(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        process.stdout.write(" NULL\n");
    }
    sort()
    {
        if (this.head == null || this.head.next == null)
        {
            // less than 2 nodes
            return;
        }
        // Auxiliary variables
        var first = null;
        var second = null;
        var point = null;
        var temp = this.head;
        var auxiliary = null;
        var count = 0;
        // Split the linked list nodes
        while (temp != null)
        {
            if (count % 2 == 0)
            {
                // Add node in first list 
                // Add node at the end of linked list
                if (first == null)
                {
                    first = temp;
                    point = temp;
                }
                else
                {
                    point.next = temp;
                    point = temp;
                }
                // Visit to next node
                temp = temp.next;
                // no next node
                point.next = null;
            }
            else
            {
                // Add node at beginning of second linked list
                // Collect new node
                auxiliary = temp;
                // Visit to next node
                temp = temp.next;
                // Connect current node to previous head of second list
                auxiliary.next = second;
                // Set first node of second list
                second = auxiliary;
            }
            count++;
        }
        auxiliary = null;
        // Combine alternating nodes in sorted order
        while (count > 0)
        {
            if (first != null && second != null)
            {
                if (first.data < second.data)
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = first;
                        auxiliary = first;
                    }
                    else
                    {
                        auxiliary.next = first;
                    }
                    auxiliary = first;
                    // Visit to next node
                    first = first.next;
                }
                else
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = second;
                        auxiliary = second;
                    }
                    else
                    {
                        auxiliary.next = second;
                    }
                    auxiliary = second;
                    // Visit to next node
                    second = second.next;
                }
            }
            else if (first != null)
            {
                // When element exists in first linked list
                auxiliary.next = first;
                // new last node
                auxiliary = first;
                // Visit to next node
                first = first.next;
            }
            else
            {
                // When element exists in second linked list
                auxiliary.next = second;
                // new last node
                auxiliary = second;
                // Visit to next node
                second = second.next;
            }
            // Set new last node
            this.tail = auxiliary;
            count--;
        }
    }
}

function main()
{
    var sll = new SingleLL();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    sll.addNode(7);
    sll.addNode(45);
    sll.addNode(15);
    sll.addNode(18);
    sll.addNode(40);
    sll.addNode(12);
    sll.addNode(60);
    sll.addNode(9);
    sll.addNode(80);
    process.stdout.write(" Before Sort :");
    sll.display();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    // Alternating ascending order
    // 7 → 15 → 40 → 60 → 80 → NULL
    // Alternating descending order
    // 45 → 18 → 12 → 9 → NULL
    // Result
    // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    sll.sort();
    process.stdout.write(" After Sort :");
    sll.display();
}
main();

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
#    Python 3 program for
#    Sort a linked list that is sorted alternating 
#    ascending and descending orders

#  Linked list node
class LinkNode :
    def __init__(self, data) :
        self.data = data
        self.next = None
    

class SingleLL :
    def __init__(self) :
        self.head = None
        self.tail = None
    
    #  Add new Node at end of linked list 
    def addNode(self, data) :
        node = LinkNode(data)
        if (self.head == None) :
            self.head = node
        else :
            #  Append the node at last position
            self.tail.next = node
        
        self.tail = node
    
    #  Display linked list element
    def display(self) :
        if (self.head == None) :
            return
        
        temp = self.head
        #  iterating linked list elements
        while (temp != None) :
            print("", temp.data ,"→", end = "")
            #  Visit to next node
            temp = temp.next
        
        print(" NULL")
    
    def sort(self) :
        if (self.head == None or self.head.next == None) :
            #  less than 2 nodes
            return
        
        #  Auxiliary variables
        first = None
        second = None
        point = None
        temp = self.head
        auxiliary = None
        count = 0
        #  Split the linked list nodes
        while (temp != None) :
            if (count % 2 == 0) :
                #  Add node in first list 
                #  Add node at the end of linked list
                if (first == None) :
                    first = temp
                    point = temp
                else :
                    point.next = temp
                    point = temp
                
                #  Visit to next node
                temp = temp.next
                #  no next node
                point.next = None
            else :
                #  Add node at beginning of second linked list
                #  Collect new node
                auxiliary = temp
                #  Visit to next node
                temp = temp.next
                #  Connect current node to previous head of second list
                auxiliary.next = second
                #  Set first node of second list
                second = auxiliary
            
            count += 1
        
        auxiliary = None
        #  Combine alternating nodes in sorted order
        while (count > 0) :
            if (first != None and second != None) :
                if (first.data < second.data) :
                    if (auxiliary == None) :
                        #  First node of resultant linked list
                        self.head = first
                        auxiliary = first
                    else :
                        auxiliary.next = first
                    
                    auxiliary = first
                    #  Visit to next node
                    first = first.next
                else :
                    if (auxiliary == None) :
                        #  First node of resultant linked list
                        self.head = second
                        auxiliary = second
                    else :
                        auxiliary.next = second
                    
                    auxiliary = second
                    #  Visit to next node
                    second = second.next
                
            elif (first != None) :
                #  When element exists in first linked list
                auxiliary.next = first
                #  new last node
                auxiliary = first
                #  Visit to next node
                first = first.next
            else :
                #  When element exists in second linked list
                auxiliary.next = second
                #  new last node
                auxiliary = second
                #  Visit to next node
                second = second.next
            
            #  Set new last node
            self.tail = auxiliary
            count -= 1
        
    

def main() :
    sll = SingleLL()
    #  Linked list
    #  7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    sll.addNode(7)
    sll.addNode(45)
    sll.addNode(15)
    sll.addNode(18)
    sll.addNode(40)
    sll.addNode(12)
    sll.addNode(60)
    sll.addNode(9)
    sll.addNode(80)
    print(" Before Sort :", end = "")
    sll.display()
    #  Linked list
    #  7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    #  Alternating ascending order
    #  7 → 15 → 40 → 60 → 80 → NULL
    #  Alternating descending order
    #  45 → 18 → 12 → 9 → NULL
    #  Result
    #  7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    sll.sort()
    print(" After Sort :", end = "")
    sll.display()

if __name__ == "__main__": main()

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
#    Ruby program for
#    Sort a linked list that is sorted alternating 
#    ascending and descending orders

#  Linked list node
class LinkNode 
    # Define the accessor and reader of class LinkNode
    attr_reader :data, :next
    attr_accessor :data, :next
    def initialize(data) 
        self.data = data
        self.next = nil
    end

end

class SingleLL 
    # Define the accessor and reader of class SingleLL
    attr_reader :head, :tail
    attr_accessor :head, :tail
    def initialize() 
        self.head = nil
        self.tail = nil
    end

    #  Add new Node at end of linked list 
    def addNode(data) 
        node = LinkNode.new(data)
        if (self.head == nil) 
            self.head = node
        else
 
            #  Append the node at last position
            self.tail.next = node
        end

        self.tail = node
    end

    #  Display linked list element
    def display() 
        if (self.head == nil) 
            return
        end

        temp = self.head
        #  iterating linked list elements
        while (temp != nil) 
            print(" ", temp.data ," →")
            #  Visit to next node
            temp = temp.next
        end

        print(" NULL\n")
    end

    def sort() 
        if (self.head == nil || self.head.next == nil) 
            #  less than 2 nodes
            return
        end

        #  Auxiliary variables
        first = nil
        second = nil
        point = nil
        temp = self.head
        auxiliary = nil
        count = 0
        #  Split the linked list nodes
        while (temp != nil) 
            if (count % 2 == 0) 
                #  Add node in first list 
                #  Add node at the end of linked list
                if (first == nil) 
                    first = temp
                    point = temp
                else
 
                    point.next = temp
                    point = temp
                end

                #  Visit to next node
                temp = temp.next
                #  no next node
                point.next = nil
            else
 
                #  Add node at beginning of second linked list
                #  Collect new node
                auxiliary = temp
                #  Visit to next node
                temp = temp.next
                #  Connect current node to previous head of second list
                auxiliary.next = second
                #  Set first node of second list
                second = auxiliary
            end

            count += 1
        end

        auxiliary = nil
        #  Combine alternating nodes in sorted order
        while (count > 0) 
            if (first != nil && second != nil) 
                if (first.data < second.data) 
                    if (auxiliary == nil) 
                        #  First node of resultant linked list
                        self.head = first
                        auxiliary = first
                    else
 
                        auxiliary.next = first
                    end

                    auxiliary = first
                    #  Visit to next node
                    first = first.next
                else
 
                    if (auxiliary == nil) 
                        #  First node of resultant linked list
                        self.head = second
                        auxiliary = second
                    else
 
                        auxiliary.next = second
                    end

                    auxiliary = second
                    #  Visit to next node
                    second = second.next
                end

            elsif (first != nil) 
                #  When element exists in first linked list
                auxiliary.next = first
                #  new last node
                auxiliary = first
                #  Visit to next node
                first = first.next
            else
 
                #  When element exists in second linked list
                auxiliary.next = second
                #  new last node
                auxiliary = second
                #  Visit to next node
                second = second.next
            end

            #  Set new last node
            self.tail = auxiliary
            count -= 1
        end

    end

end

def main() 
    sll = SingleLL.new()
    #  Linked list
    #  7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    sll.addNode(7)
    sll.addNode(45)
    sll.addNode(15)
    sll.addNode(18)
    sll.addNode(40)
    sll.addNode(12)
    sll.addNode(60)
    sll.addNode(9)
    sll.addNode(80)
    print(" Before Sort :")
    sll.display()
    #  Linked list
    #  7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    #  Alternating ascending order
    #  7 → 15 → 40 → 60 → 80 → NULL
    #  Alternating descending order
    #  45 → 18 → 12 → 9 → NULL
    #  Result
    #  7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    sll.sort()
    print(" After Sort :")
    sll.display()
end

main()

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
/*
    Scala program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
class LinkNode(var data: Int,
    var next: LinkNode)
{
    def this(data: Int)
    {
        this(data, null);
    }
}
class SingleLL(var head: LinkNode,
    var tail: LinkNode)
{
    def this()
    {
        this(null, null);
    }
    // Add new Node at end of linked list 
    def addNode(data: Int): Unit = {
        var node: LinkNode = new LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    def display(): Unit = {
        if (this.head == null)
        {
            return;
        }
        var temp: LinkNode = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        print(" NULL\n");
    }
    def sort(): Unit = {
        if (this.head == null || this.head.next == null)
        {
            // less than 2 nodes
            return;
        }
        // Auxiliary variables
        var first: LinkNode = null;
        var second: LinkNode = null;
        var point: LinkNode = null;
        var temp: LinkNode = this.head;
        var auxiliary: LinkNode = null;
        var count: Int = 0;
        // Split the linked list nodes
        while (temp != null)
        {
            if (count % 2 == 0)
            {
                // Add node in first list 
                // Add node at the end of linked list
                if (first == null)
                {
                    first = temp;
                    point = temp;
                }
                else
                {
                    point.next = temp;
                    point = temp;
                }
                // Visit to next node
                temp = temp.next;
                // no next node
                point.next = null;
            }
            else
            {
                // Add node at beginning of second linked list
                // Collect new node
                auxiliary = temp;
                // Visit to next node
                temp = temp.next;
                // Connect current node to previous head of second list
                auxiliary.next = second;
                // Set first node of second list
                second = auxiliary;
            }
            count += 1;
        }
        auxiliary = null;
        // Combine alternating nodes in sorted order
        while (count > 0)
        {
            if (first != null && second != null)
            {
                if (first.data < second.data)
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = first;
                        auxiliary = first;
                    }
                    else
                    {
                        auxiliary.next = first;
                    }
                    auxiliary = first;
                    // Visit to next node
                    first = first.next;
                }
                else
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = second;
                        auxiliary = second;
                    }
                    else
                    {
                        auxiliary.next = second;
                    }
                    auxiliary = second;
                    // Visit to next node
                    second = second.next;
                }
            }
            else if (first != null)
            {
                // When element exists in first linked list
                auxiliary.next = first;
                // new last node
                auxiliary = first;
                // Visit to next node
                first = first.next;
            }
            else
            {
                // When element exists in second linked list
                auxiliary.next = second;
                // new last node
                auxiliary = second;
                // Visit to next node
                second = second.next;
            }
            // Set new last node
            this.tail = auxiliary;
            count -= 1;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var sll: SingleLL = new SingleLL();
        // Linked list
        // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
        sll.addNode(7);
        sll.addNode(45);
        sll.addNode(15);
        sll.addNode(18);
        sll.addNode(40);
        sll.addNode(12);
        sll.addNode(60);
        sll.addNode(9);
        sll.addNode(80);
        print(" Before Sort :");
        sll.display();
        // Linked list
        // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
        // Alternating ascending order
        // 7 → 15 → 40 → 60 → 80 → NULL
        // Alternating descending order
        // 45 → 18 → 12 → 9 → NULL
        // Result
        // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
        sll.sort();
        print(" After Sort :");
        sll.display();
    }
}

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
/*
    Swift 4 program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
class LinkNode
{
    var data: Int;
    var next: LinkNode? ;
    init(_ data: Int)
    {
        self.data = data;
        self.next = nil;
    }
}
class SingleLL
{
    var head: LinkNode? ;
    var tail: LinkNode? ;
    init()
    {
        self.head = nil;
        self.tail = nil;
    }
    // Add new Node at end of linked list 
    func addNode(_ data: Int)
    {
        let node: LinkNode = LinkNode(data);
        if (self.head == nil)
        {
            self.head = node;
        }
        else
        {
            // Append the node at last position
            self.tail!.next = node;
        }
        self.tail = node;
    }
    // Display linked list element
    func display()
    {
        if (self.head == nil)
        {
            return;
        }
        var temp: LinkNode? = self.head;
        // iterating linked list elements
        while (temp  != nil)
        {
            print("", temp!.data ,"→", terminator: "");
            // Visit to next node
            temp = temp!.next;
        }
        print(" NULL");
    }
    func sort()
    {
        if (self.head == nil || self.head!.next == nil)
        {
            // less than 2 nodes
            return;
        }
        // Auxiliary variables
        var first: LinkNode? = nil;
        var second: LinkNode? = nil;
        var point: LinkNode? = nil;
        var temp: LinkNode? = self.head;
        var auxiliary: LinkNode? = nil;
        var count: Int = 0;
        // Split the linked list nodes
        while (temp  != nil)
        {
            if (count % 2 == 0)
            {
                // Add node in first list 
                // Add node at the end of linked list
                if (first == nil)
                {
                    first = temp;
                    point = temp;
                }
                else
                {
                    point!.next = temp;
                    point = temp;
                }
                // Visit to next node
                temp = temp!.next;
                // no next node
                point!.next = nil;
            }
            else
            {
                // Add node at beginning of second linked list
                // Collect new node
                auxiliary = temp;
                // Visit to next node
                temp = temp!.next;
                // Connect current node to previous head of second list
                auxiliary!.next = second;
                // Set first node of second list
                second = auxiliary;
            }
            count += 1;
        }
        auxiliary = nil;
        // Combine alternating nodes in sorted order
        while (count > 0)
        {
            if (first  != nil && second  != nil)
            {
                if (first!.data < second!.data)
                {
                    if (auxiliary == nil)
                    {
                        // First node of resultant linked list
                        self.head = first;
                        auxiliary = first;
                    }
                    else
                    {
                        auxiliary!.next = first;
                    }
                    auxiliary = first;
                    // Visit to next node
                    first = first!.next;
                }
                else
                {
                    if (auxiliary == nil)
                    {
                        // First node of resultant linked list
                        self.head = second;
                        auxiliary = second;
                    }
                    else
                    {
                        auxiliary!.next = second;
                    }
                    auxiliary = second;
                    // Visit to next node
                    second = second!.next;
                }
            }
            else if (first  != nil)
            {
                // When element exists in first linked list
                auxiliary!.next = first;
                // new last node
                auxiliary = first;
                // Visit to next node
                first = first!.next;
            }
            else
            {
                // When element exists in second linked list
                auxiliary!.next = second;
                // new last node
                auxiliary = second;
                // Visit to next node
                second = second!.next;
            }
            // Set new last node
            self.tail = auxiliary;
            count -= 1;
        }
    }
}
func main()
{
    let sll: SingleLL = SingleLL();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    sll.addNode(7);
    sll.addNode(45);
    sll.addNode(15);
    sll.addNode(18);
    sll.addNode(40);
    sll.addNode(12);
    sll.addNode(60);
    sll.addNode(9);
    sll.addNode(80);
    print(" Before Sort :", terminator: "");
    sll.display();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    // Alternating ascending order
    // 7 → 15 → 40 → 60 → 80 → NULL
    // Alternating descending order
    // 45 → 18 → 12 → 9 → NULL
    // Result
    // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    sll.sort();
    print(" After Sort :", terminator: "");
    sll.display();
}
main();

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
/*
    Kotlin program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
class LinkNode
{
    var data: Int;
    var next: LinkNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.next = null;
    }
}
class SingleLL
{
    var head: LinkNode ? ;
    var tail: LinkNode ? ;
    constructor()
    {
        this.head = null;
        this.tail = null;
    }
    // Add new Node at end of linked list 
    fun addNode(data: Int): Unit
    {
        val node: LinkNode = LinkNode(data);
        if (this.head == null)
        {
            this.head = node;
        }
        else
        {
            // Append the node at last position
            this.tail?.next = node;
        }
        this.tail = node;
    }
    // Display linked list element
    fun display(): Unit
    {
        if (this.head == null)
        {
            return;
        }
        var temp: LinkNode ? = this.head;
        // iterating linked list elements
        while (temp != null)
        {
            print(" " + temp.data + " →");
            // Visit to next node
            temp = temp.next;
        }
        print(" NULL\n");
    }
    fun sort(): Unit
    {
        if (this.head == null || this.head?.next == null)
        {
            // less than 2 nodes
            return;
        }
        // Auxiliary variables
        var first: LinkNode ? = null;
        var second: LinkNode ? = null;
        var point: LinkNode ? = null;
        var temp: LinkNode ? = this.head;
        var auxiliary: LinkNode ? ;
        var count: Int = 0;
        // Split the linked list nodes
        while (temp != null)
        {
            if (count % 2 == 0)
            {
                // Add node in first list 
                // Add node at the end of linked list
                if (first == null)
                {
                    first = temp;
                    point = temp;
                }
                else
                {
                    point?.next = temp;
                    point = temp;
                }
                // Visit to next node
                temp = temp.next;
                // no next node
                point.next = null;
            }
            else
            {
                // Add node at beginning of second linked list
                // Collect new node
                auxiliary = temp;
                // Visit to next node
                temp = temp.next;
                // Connect current node to previous head of second list
                auxiliary.next = second;
                // Set first node of second list
                second = auxiliary;
            }
            count += 1;
        }
        auxiliary = null;
        // Combine alternating nodes in sorted order
        while (count > 0)
        {
            if (first != null && second != null)
            {
                if (first.data < second.data)
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = first;
                    }
                    else
                    {
                        auxiliary.next = first;
                    }
                    auxiliary = first;
                    // Visit to next node
                    first = first.next;
                }
                else
                {
                    if (auxiliary == null)
                    {
                        // First node of resultant linked list
                        this.head = second;
                    }
                    else
                    {
                        auxiliary.next = second;
                    }
                    auxiliary = second;
                    // Visit to next node
                    second = second.next;
                }
            }
            else if (first != null)
            {
                // When element exists in first linked list
                auxiliary?.next = first;
                // new last node
                auxiliary = first;
                // Visit to next node
                first = first.next;
            }
            else
            {
                // When element exists in second linked list
                auxiliary?.next = second;
                // new last node
                auxiliary = second;
                // Visit to next node
                second = second?.next;
            }
            // Set new last node
            this.tail = auxiliary;
            count -= 1;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val sll: SingleLL = SingleLL();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    sll.addNode(7);
    sll.addNode(45);
    sll.addNode(15);
    sll.addNode(18);
    sll.addNode(40);
    sll.addNode(12);
    sll.addNode(60);
    sll.addNode(9);
    sll.addNode(80);
    print(" Before Sort :");
    sll.display();
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    // Alternating ascending order
    // 7 → 15 → 40 → 60 → 80 → NULL
    // Alternating descending order
    // 45 → 18 → 12 → 9 → NULL
    // Result
    // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    sll.sort();
    print(" After Sort :");
    sll.display();
}

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
package main
import "fmt"
/*
    Go program for
    Sort a linked list that is sorted alternating 
    ascending and descending orders
*/
// Linked list node
type LinkNode struct {
    data int
    next * LinkNode
}
func getLinkNode(data int) * LinkNode {
    var me *LinkNode = &LinkNode {}
    me.data = data
    me.next = nil
    return me
}
type SingleLL struct {
    head * LinkNode
    tail * LinkNode
}
func getSingleLL() * SingleLL {
    var me *SingleLL = &SingleLL {}
    me.head = nil
    me.tail = nil
    return me
}
// Add new Node at end of linked list 
func(this *SingleLL) addNode(data int) {
    var node * LinkNode = getLinkNode(data)
    if this.head == nil {
        this.head = node
    } else {
        // Append the node at last position
        this.tail.next = node
    }
    this.tail = node
}
// Display linked list element
func(this SingleLL) display() {
    if this.head == nil {
        return
    }
    var temp * LinkNode = this.head
    // iterating linked list elements
    for (temp != nil) {
        fmt.Print(" ", temp.data, " →")
        // Visit to next node
        temp = temp.next
    }
    fmt.Print(" NULL\n")
}
func(this SingleLL) sort() {
    if this.head == nil || this.head.next == nil {
        // less than 2 nodes
        return
    }
    // Auxiliary variables
    var first * LinkNode = nil
    var second * LinkNode = nil
    var point * LinkNode = nil
    var temp * LinkNode = this.head
    var auxiliary * LinkNode = nil
    var count int = 0
    // Split the linked list nodes
    for (temp != nil) {
        if count % 2 == 0 {
            // Add node in first list 
            // Add node at the end of linked list
            if first == nil {
                first = temp
                point = temp
            } else {
                point.next = temp
                point = temp
            }
            // Visit to next node
            temp = temp.next
            // no next node
            point.next = nil
        } else {
            // Add node at beginning of second linked list
            // Collect new node
            auxiliary = temp
            // Visit to next node
            temp = temp.next
            // Connect current node to previous head of second list
            auxiliary.next = second
            // Set first node of second list
            second = auxiliary
        }
        count++
    }
    auxiliary = nil
    // Combine alternating nodes in sorted order
    for (count > 0) {
        if first != nil && second != nil {
            if first.data < second.data {
                if auxiliary == nil {
                    // First node of resultant linked list
                    this.head = first
                } else {
                    auxiliary.next = first
                }
                auxiliary = first
                // Visit to next node
                first = first.next
            } else {
                if auxiliary == nil {
                    // First node of resultant linked list
                    this.head = second
                } else {
                    auxiliary.next = second
                }
                auxiliary = second
                // Visit to next node
                second = second.next
            }
        } else if first != nil {
            // When element exists in first linked list
            auxiliary.next = first
            // new last node
            auxiliary = first
            // Visit to next node
            first = first.next
        } else {
            // When element exists in second linked list
            auxiliary.next = second
            // new last node
            auxiliary = second
            // Visit to next node
            second = second.next
        }
        // Set new last node
        this.tail = auxiliary
        count--
    }
}
func main() {
    var sll * SingleLL = getSingleLL()
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    sll.addNode(7)
    sll.addNode(45)
    sll.addNode(15)
    sll.addNode(18)
    sll.addNode(40)
    sll.addNode(12)
    sll.addNode(60)
    sll.addNode(9)
    sll.addNode(80)
    fmt.Print(" Before Sort :")
    sll.display()
    // Linked list
    // 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
    // Alternating ascending order
    // 7 → 15 → 40 → 60 → 80 → NULL
    // Alternating descending order
    // 45 → 18 → 12 → 9 → NULL
    // Result
    // 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL
    sll.sort()
    fmt.Print(" After Sort :")
    sll.display()
}

Output

 Before Sort : 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
 After Sort : 7 → 9 → 12 → 15 → 18 → 40 → 45 → 60 → 80 → NULL


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved