# 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>

{
int data;
};
struct SingleLL
{
};
// Returns the new linked list
{
// 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->tail = NULL;
}
return sll;
}
void addNode(struct SingleLL *sll, int data)
{
// Create dynamic node
if (node == NULL)
{
return;
}
else
{
// Set initial node value
node->data = data;
node->next = NULL;
}
{
}
else
{
sll->tail->next = node;
}
sll->tail = node;
}
{
if (node == NULL)
{
return;
}
while (temp != NULL)
{
printf(" %d →", temp->data);
// Visit to next node
temp = temp->next;
}
printf(" NULL\n");
}
void sort(struct SingleLL *sll)
{
{
// less than 2 nodes
return;
}
// Auxiliary variables
int count = 0;
// Split the linked list nodes
while (temp != NULL)
{
if (count % 2 == 0)
{
// Add node in first 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
{
// 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
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
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[])
{
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
printf(" Before Sort :");
// 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 :");
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``````
``````/*
Java program for
Sort a linked list that is sorted alternating
ascending and descending orders
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
System.out.print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
System.out.print(" NULL\n");
}
public void sort()
{
{
// less than 2 nodes
return;
}
// Auxiliary variables
int count = 0;
// Split the linked list nodes
while (temp != null)
{
if (count % 2 == 0)
{
// Add node in first 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
{
// 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
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
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();
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
System.out.print(" Before Sort :");
sll.display();
// 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
*/
{
public: int data;
{
this->data = data;
this->next = NULL;
}
};
class SingleLL
{
SingleLL()
{
this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
this->tail->next = node;
}
this->tail = node;
}
void display()
{
{
return;
}
while (temp != NULL)
{
cout << " " << temp->data << " →";
// Visit to next node
temp = temp->next;
}
cout << " NULL\n";
}
void sort()
{
{
// less than 2 nodes
return;
}
// Auxiliary variables
int count = 0;
// Split the linked list nodes
while (temp != NULL)
{
if (count % 2 == 0)
{
// Add node in first 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
{
// 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
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
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();
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
cout << " Before Sort :";
sll->display();
// 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
*/
{
public int data;
{
this.data = data;
this.next = null;
}
}
public class SingleLL
{
public SingleLL()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
public void display()
{
{
return;
}
while (temp != null)
{
Console.Write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
Console.Write(" NULL\n");
}
public void sort()
{
{
// less than 2 nodes
return;
}
// Auxiliary variables
int count = 0;
// Split the linked list nodes
while (temp != null)
{
if (count % 2 == 0)
{
// Add node in first 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
{
// 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
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
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();
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
Console.Write(" Before Sort :");
sll.display();
// 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
*/
{
public \$data;
public \$next;
public  function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
class SingleLL
{
public \$tail;
public  function __construct()
{
\$this->tail = NULL;
}
{
{
}
else
{
// Append the node at last position
\$this->tail->next = \$node;
}
\$this->tail = \$node;
}
public  function display()
{
{
return;
}
while (\$temp != NULL)
{
echo(" ".\$temp->data.
" →");
// Visit to next node
\$temp = \$temp->next;
}
echo(" NULL\n");
}
public  function sort()
{
{
// less than 2 nodes
return;
}
// Auxiliary variables
\$first = NULL;
\$second = NULL;
\$point = NULL;
\$auxiliary = NULL;
\$count = 0;
// Split the linked list nodes
while (\$temp != NULL)
{
if (\$count % 2 == 0)
{
// Add node in first 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
{
// 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
\$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
\$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();
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
echo(" Before Sort :");
\$sll->display();
// 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
*/
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
display()
{
{
return;
}
while (temp != null)
{
process.stdout.write(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
process.stdout.write(" NULL\n");
}
sort()
{
{
// less than 2 nodes
return;
}
// Auxiliary variables
var first = null;
var second = null;
var point = null;
var auxiliary = null;
var count = 0;
// Split the linked list nodes
while (temp != null)
{
if (count % 2 == 0)
{
// Add node in first 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
{
// 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
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
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();
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
process.stdout.write(" Before Sort :");
sll.display();
// 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

def __init__(self, data) :
self.data = data
self.next = None

class SingleLL :
def __init__(self) :
self.tail = None

else :
#  Append the node at last position
self.tail.next = node

self.tail = node

def display(self) :
return

while (temp != None) :
print("", temp.data ,"→", end = "")
#  Visit to next node
temp = temp.next

print(" NULL")

def sort(self) :
#  less than 2 nodes
return

#  Auxiliary variables
first = None
second = None
point = None
auxiliary = None
count = 0
#  Split the linked list nodes
while (temp != None) :
if (count % 2 == 0) :
#  Add node in first 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 :
#  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
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
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()
#  7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
print(" Before Sort :", end = "")
sll.display()
#  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

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
def initialize()
self.tail = nil
end

else

#  Append the node at last position
self.tail.next = node
end

self.tail = node
end

def display()
return
end

while (temp != nil)
print(" ", temp.data ," →")
#  Visit to next node
temp = temp.next
end

print(" NULL\n")
end

def sort()
#  less than 2 nodes
return
end

#  Auxiliary variables
first = nil
second = nil
point = nil
auxiliary = nil
count = 0
#  Split the linked list nodes
while (temp != nil)
if (count % 2 == 0)
#  Add node in first 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

#  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
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
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()
#  7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
print(" Before Sort :")
sll.display()
#  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
*/
{
def this(data: Int)
{
this(data, null);
}
}
{
def this()
{
this(null, null);
}
def addNode(data: Int): Unit = {
{
}
else
{
// Append the node at last position
this.tail.next = node;
}
this.tail = node;
}
def display(): Unit = {
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
def sort(): Unit = {
{
// less than 2 nodes
return;
}
// Auxiliary variables
var count: Int = 0;
// Split the linked list nodes
while (temp != null)
{
if (count % 2 == 0)
{
// Add node in first 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
{
// 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
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
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();
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
print(" Before Sort :");
sll.display();
// 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
*/
{
var data: Int;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class SingleLL
{
init()
{
self.tail = nil;
}
{
{
}
else
{
// Append the node at last position
self.tail!.next = node;
}
self.tail = node;
}
func display()
{
{
return;
}
while (temp  != nil)
{
print("", temp!.data ,"→", terminator: "");
// Visit to next node
temp = temp!.next;
}
print(" NULL");
}
func sort()
{
{
// less than 2 nodes
return;
}
// Auxiliary variables
var count: Int = 0;
// Split the linked list nodes
while (temp  != nil)
{
if (count % 2 == 0)
{
// Add node in first 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
{
// 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
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
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();
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
print(" Before Sort :", terminator: "");
sll.display();
// 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
*/
{
var data: Int;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class SingleLL
{
constructor()
{
this.tail = null;
}
{
{
}
else
{
// Append the node at last position
this.tail?.next = node;
}
this.tail = node;
}
fun display(): Unit
{
{
return;
}
while (temp != null)
{
print(" " + temp.data + " →");
// Visit to next node
temp = temp.next;
}
print(" NULL\n");
}
fun sort(): Unit
{
{
// less than 2 nodes
return;
}
// Auxiliary variables
var first: LinkNode ? = null;
var second: LinkNode ? = null;
var point: LinkNode ? = null;
var count: Int = 0;
// Split the linked list nodes
while (temp != null)
{
if (count % 2 == 0)
{
// Add node in first 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
{
// 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
}
else
{
auxiliary.next = first;
}
auxiliary = first;
// Visit to next node
first = first.next;
}
else
{
if (auxiliary == null)
{
// First node of resultant linked list
}
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();
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
print(" Before Sort :");
sll.display();
// 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
*/
data int
}
me.data = data
me.next = nil
return me
}
type SingleLL struct {
}
func getSingleLL() * SingleLL {
var me *SingleLL = &SingleLL {}
me.tail = nil
return me
}
} else {
// Append the node at last position
this.tail.next = node
}
this.tail = node
}
func(this SingleLL) display() {
return
}
for (temp != nil) {
fmt.Print(" ", temp.data, " →")
// Visit to next node
temp = temp.next
}
fmt.Print(" NULL\n")
}
func(this SingleLL) sort() {
// less than 2 nodes
return
}
// Auxiliary variables
var first * LinkNode = nil
var second * LinkNode = nil
var point * LinkNode = nil
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
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 {
// 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
} else {
auxiliary.next = first
}
auxiliary = first
// Visit to next node
first = first.next
} else {
if auxiliary == nil {
// First node of resultant linked list
} 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()
// 7 → 45 → 15 → 18 → 40 → 12 → 60 → 9 → 80 → NULL
fmt.Print(" Before Sort :")
sll.display()
// 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``````

## Comment

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.