CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
Program to sort the elements of the singly linked listExplanationIn this program, we need to sort the nodes of the given singly linked list in ascending order. Original list: Sorted list: To accomplish this task, we maintain two pointers: current and index. Initially, current point to head node and index will point to node next to current. Traverse through the list till current points to null, by comparing current's data with index's data. If current's data is greater than the index's data, then swap data between them. In the above example, current will initially point to 9 and index will point to 7. Since, 9 is greater than 7, swap the data. Continue this process until the entire list is sorted in ascending order. Algorithm
SolutionPython#Represent a node of the singly linked list class Node: def __init__(self,data): self.data = data; self.next = None; class SortList: #Represent the head and tail of the singly linked list def __init__(self): self.head = None; self.tail = None; #addNode() will add a new node to the list def addNode(self, data): #Create a new node newNode = Node(data); #Checks if the list is empty if(self.head == None): #If list is empty, both head and tail will point to new node self.head = newNode; self.tail = newNode; else: #newNode will be added after tail such that tail's next will point to newNode self.tail.next = newNode; #newNode will become new tail of the list self.tail = newNode; #sortList() will sort nodes of the list in ascending order def sortList(self): #Node current will point to head current = self.head; index = None; if(self.head == None): return; else: while(current != None): #Node index will point to node next to current index = current.next; while(index != None): #If current node's data is greater than index's node data, swap the data between them if(current.data > index.data): temp = current.data; current.data = index.data; index.data = temp; index = index.next; current = current.next; #display() will display all the nodes present in the list def display(self): #Node current will point to head current = self.head; if(self.head == None): print("List is empty"); return; while(current != None): #Prints each node by incrementing pointer print(current.data), current = current.next; print "" sList = SortList(); #Adds data to the list sList.addNode(9); sList.addNode(7); sList.addNode(2); sList.addNode(5); sList.addNode(4); #Displaying original list print("Original list: "); sList.display(); #Sorting list sList.sortList(); #Displaying sorted list print("Sorted list: "); sList.display(); Output: Original list: 9 7 2 5 4 Sorted list: 2 4 5 7 9 C#include <stdio.h> //Represent a node of the singly linked list struct node{ int data; struct node *next; }; //Represent the head and tail of the singly linked list struct node *head, *tail = NULL; //addNode() will add a new node to the list void addNode(int data) { //Create a new node struct node *newNode = (struct node*)malloc(sizeof(struct node)); newNode>data = data; newNode>next = NULL; //Checks if the list is empty if(head == NULL) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail>next = newNode; //newNode will become new tail of the list tail = newNode; } } //sortList() will sort nodes of the list in ascending order void sortList() { //Node current will point to head struct node *current = head, *index = NULL; int temp; if(head == NULL) { return; } else { while(current != NULL) { //Node index will point to node next to current index = current>next; while(index != NULL) { //If current node's data is greater than index's node data, swap the data between them if(current>data > index>data) { temp = current>data; current>data = index>data; index>data = temp; } index = index>next; } current = current>next; } } } //display() will display all the nodes present in the list void display() { //Node current will point to head struct node *current = head; if(head == NULL) { printf("List is empty \n"); return; } while(current != NULL) { //Prints each node by incrementing pointer printf("%d ", current>data); current = current>next; } printf("\n"); } int main() { //Adds data to the list addNode(9); addNode(7); addNode(2); addNode(5); addNode(4); //Displaying original list printf("Original list: \n"); display(); //Sorting list sortList(); //Displaying sorted list printf("Sorted list: \n"); display(); return 0; } Output: Original list: 9 7 2 5 4 Sorted list: 2 4 5 7 9 JAVApublic class SortList { //Represent a node of the singly linked list class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Represent the head and tail of the singly linked list public Node head = null; public Node tail = null; //addNode() will add a new node to the list public void addNode(int data) { //Create a new node Node newNode = new Node(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode will become new tail of the list tail = newNode; } } //sortList() will sort nodes of the list in ascending order public void sortList() { //Node current will point to head Node current = head, index = null; int temp; if(head == null) { return; } else { while(current != null) { //Node index will point to node next to current index = current.next; while(index != null) { //If current node's data is greater than index's node data, swap the data between them if(current.data > index.data) { temp = current.data; current.data = index.data; index.data = temp; } index = index.next; } current = current.next; } } } //display() will display all the nodes present in the list public void display() { //Node current will point to head Node current = head; if(head == null) { System.out.println("List is empty"); return; } while(current != null) { //Prints each node by incrementing pointer System.out.print(current.data + " "); current = current.next; } System.out.println(); } public static void main(String[] args) { SortList sList = new SortList(); //Adds data to the list sList.addNode(9); sList.addNode(7); sList.addNode(2); sList.addNode(5); sList.addNode(4); //Displaying original list System.out.println("Original list: "); sList.display(); //Sorting list sList.sortList(); //Displaying sorted list System.out.println("Sorted list: "); sList.display(); } } Output: Original list: 9 7 2 5 4 Sorted list: 2 4 5 7 9 C#using System; public class CreateList { //Represent a node of the singly linked list public class Node<T>{ public T data; public Node<T> next; public Node(T value) { data = value; next = null; } } public class SortList<T> where T : IComparable<T>{ //Represent the head and tail of the singly linked list public Node<T> head = null; public Node<T> tail = null; //addNode() will add a new node to the list public void addNode(T data) { //Create a new node Node<T> newNode = new Node<T>(data); //Checks if the list is empty if(head == null) { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode will become new tail of the list tail = newNode; } } //sortList() will sort nodes of the list in ascending order public void sortList() { //Node current will point to head Node<T> current = head, index = null; T temp; if(head == null) { return; } else { while(current != null) { //Node index will point to node next to current index = current.next; while(index != null) { //If current node's data is greater than index's node data, swap the data between them if(current.data.CompareTo(index.data) > 0) { temp = current.data; current.data = index.data; index.data = temp; } index = index.next; } current = current.next; } } } //display() will display all the nodes present in the list public void display() { //Node current will point to head Node<T> current = head; if(head == null) { Console.WriteLine("List is empty"); return; } while(current != null) { //Prints each node by incrementing pointer Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); } } public static void Main() { SortList<int> sList = new SortList<int>(); //Adds data to the list sList.addNode(9); sList.addNode(7); sList.addNode(2); sList.addNode(5); sList.addNode(4); //Displaying original list Console.WriteLine("Original list: "); sList.display(); //Sorting list sList.sortList(); //Displaying sorted list Console.WriteLine("Sorted list: "); sList.display(); } } Output: Original list: 9 7 2 5 4 Sorted list: 2 4 5 7 9 PHP<!DOCTYPE html> <html> <body> <?php //Represent a node of singly linked list class Node{ public $data; public $next; function __construct($data){ $this>data = $data; $this>next = NULL; } } class SortList{ //Represent the head and tail of the singly linked list public $head; public $tail; function __construct(){ $this>head = NULL; $this>tail = NULL; } //addNode() will add a new node to the list function addNode($data) { //Create a new node $newNode = new Node($data); //Checks if the list is empty if($this>head == NULL) { //If list is empty, both head and tail will point to new node $this>head = $newNode; $this>tail = $newNode; } else { //newNode will be added after tail such that tail's next will point to newNode $this>tail>next = $newNode; //newNode will become new tail of the list $this>tail = $newNode; } } //sortList() will sort nodes of the list in ascending order function sortList() { //Node current will point to head $current = $this>head; $index = null; if($this>head == null) { return; } else { while($current != null) { //Node index will point to node next to current $index = $current>next; while($index != null) { //If current node's data is greater than index's node data, swap the data between them if($current>data > $index>data) { $temp = $current>data; $current>data = $index>data; $index>data = $temp; } $index = $index>next; } $current = $current>next; } } } //display() will display all the nodes present in the list function display() { //Node current will point to head $current = $this>head; if($this>head == NULL) { print("List is empty <br>"); return; } while($current != NULL) { //Prints each node by incrementing pointer print($current>data . " "); $current = $current>next; } print("<br>"); } } $sList = new SortList(); //Adds data to the list $sList>addNode(9); $sList>addNode(7); $sList>addNode(2); $sList>addNode(5); $sList>addNode(4); //Displaying original list print("Original list: <br>"); $sList>display(); //Sorting list $sList>sortList(); //Displaying sorted list print("Sorted list: <br>"); $sList>display(); ?> </body> </html> Output: Original list: 9 7 2 5 4 Sorted list: 2 4 5 7 9
Next Topic#
