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;
}
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 → NULLpackage 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