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

Last Updated on March 10, 2022 by Ria Pathak

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

According to the problem statement, our task is to sort a linked list that is sorted alternating ascending and descending orders.

Problem Statement Understanding

Let’s try to understand the problem statement with of an example by referring competitive programming online course.

We have been given a linked list which is sorted alternating ascending and descending orders. We can understand this statement with an example:

1 → 40 → 5 → 30 → 6 → 12 → 20 → NULL

1, 5, 6, 20 these nodes are present in the linked list in ascending order, and 40, 30, 12 are present in descending order in the linked list. These nodes are present in alternating positions in the linked list.
Our task is to sort the linked list such that after sorting, the final sorted linked list will be:
1 → 5 → 6 → 12 → 20 → 30 → 40 → NULL

Now I think from the above example, the problem statement is clear. So let’s see how we will approach it.

A straightforward approach is to sort the linked list using the merge sort algorithm, but the only problem is that here we are not utilizing the information given to us in the problem that the linked list is already sorted in alternating ascending and descending orders.

If we are using merge sort to sort the linked list the time complexity will be O(NlogN), so now we will try to think can we utilize the information given to us in the problem and will try to solve the problem in lower time complexity.

Before jumping to the approach, try to think how you can approach this problem. If stuck, no problem, we will thoroughly see how we can approach the problem in the next section.

Let’s move on to the approach section.

Approach

We have to divide the problem into three steps:

The first step is to split the linked list into two linked lists. One list is for nodes in ascending order and the second is for nodes in descending order.
After this step, We have to reverse the second linked list to change its order from descending to ascending.
After this step our both linked lists are sorted in ascending order, Now merge both lists into a single list in such fashion that the final list will also remain sorted.

Algorithm

We have to divide this problem into three steps.
The first step is to split the linked list into two lists.
Initialize two pointer variables of the type node.
One pointer for nodes of ascending order and another is for nodes in descending order.
Now we will have two lists, one is sorted in ascending order and another list is sorted in descending order.
Now reverse the second list. This will make the second linked list sorted in ascending order.
Now we have two sorted linked lists.
Merge both the linked list.
The final linked list after merging both the linked lists will be our resultant linked list.

Code Implementation

#include <bits stdc++.h="">

using namespace std;

// Linked list node

struct Node {

int data;

struct Node* next;

};

Node* mergelist(Node* head1, Node* head2);

void splitList(Node* head, Node** Ahead, Node** Dhead);

void reverselist(Node*& head);

// the function that sorts the

// linked list

void sort(Node** head){

// Split the linked list into lists

Node *Ahead, *Dhead;

splitList(*head, &Ahead, &Dhead);

// Reverse the descending ordered linked list into ascending order

reverselist(Dhead);

// Merge both linked lists

*head = mergelist(Ahead, Dhead);

}

// A function to create a new node

Node* newNode(int data)

{

Node* temp = new Node;

temp->data = data;

temp->next = NULL;

return temp;

}

// function to reverse a linked list

void reverselist(Node*& head){

Node *prev = NULL, *curr = head, *next;

while (curr) {

next = curr->next;

curr->next = prev;

prev = curr;

curr = next;

}

head = prev;

}

// function to print a linked list

void printlist(Node* head){

while (head != NULL) {

cout << head->data << " ";

head = head->next;

}

cout << endl;

}

// A function to merge two sorted linked lists

Node* mergelist(Node* head1, Node* head2)

{

// Base cases

if (!head1)

return head2;

if (!head2)

return head1;

Node* temp = NULL;

if (head1->data < head2->data) {

temp = head1;

head1->next = mergelist(head1->next, head2);

}

else {

temp = head2;

head2->next = mergelist(head1, head2->next);

}

return temp;

}

// This function alternatively splits

// a linked list into two lists.

// "Ahead" is pointer to head of ascending linked list

// "Dhead" is pointer to head of descending linked list

void splitList(Node* head, Node** Ahead, Node** Dhead){

// Create two dummy nodes to initialize

// heads of two linked list

*Ahead = newNode(0);

*Dhead = newNode(0);

Node* ascn = *Ahead;

Node* dscn = *Dhead;

Node* curr = head;

// Link alternate nodes

while (curr) {

// Link alternate nodes of ascending linked list

ascn->next = curr;

ascn = ascn->next;

curr = curr->next;

// Link alternate nodes of descending linked list

if (curr) {

dscn->next = curr;

dscn = dscn->next;

curr = curr->next;

}

ascn->next = NULL;

dscn->next = NULL;

*Ahead = (*Ahead)->next;

*Dhead = (*Dhead)->next;

}

int main()

{

Node* head = newNode(1);

head->next = newNode(9);

head->next->next = newNode(5);

head->next->next->next = newNode(8);

head->next->next->next->next = newNode(7);

cout << "Input linked list" << endl;

printlist(head);

sort(&head);

cout << "Final Sorted Linked List " << endl;

printlist(head);

return 0;

}

#include <bits stdc++.h=""> using namespace std; // Linked list node struct Node { int data; struct Node* next; }; Node* mergelist(Node* head1, Node* head2); void splitList(Node* head, Node** Ahead, Node** Dhead); void reverselist(Node*& head); // the function that sorts the // linked list void sort(Node** head){ // Split the linked list into lists Node *Ahead, *Dhead; splitList(*head, &Ahead, &Dhead); // Reverse the descending ordered linked list into ascending order reverselist(Dhead); // Merge both linked lists *head = mergelist(Ahead, Dhead); } // A function to create a new node Node* newNode(int data) { Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; } // function to reverse a linked list void reverselist(Node*& head){ Node *prev = NULL, *curr = head, *next; while (curr) { next = curr->next; curr->next = prev; prev = curr; curr = next; } head = prev; } // function to print a linked list void printlist(Node* head){ while (head != NULL) { cout << head->data << " "; head = head->next; } cout << endl; } // A function to merge two sorted linked lists Node* mergelist(Node* head1, Node* head2) { // Base cases if (!head1) return head2; if (!head2) return head1; Node* temp = NULL; if (head1->data < head2->data) { temp = head1; head1->next = mergelist(head1->next, head2); } else { temp = head2; head2->next = mergelist(head1, head2->next); } return temp; } // This function alternatively splits // a linked list into two lists. // "Ahead" is pointer to head of ascending linked list // "Dhead" is pointer to head of descending linked list void splitList(Node* head, Node** Ahead, Node** Dhead){ // Create two dummy nodes to initialize // heads of two linked list *Ahead = newNode(0); *Dhead = newNode(0); Node* ascn = *Ahead; Node* dscn = *Dhead; Node* curr = head; // Link alternate nodes while (curr) { // Link alternate nodes of ascending linked list ascn->next = curr; ascn = ascn->next; curr = curr->next; // Link alternate nodes of descending linked list if (curr) { dscn->next = curr; dscn = dscn->next; curr = curr->next; } } ascn->next = NULL; dscn->next = NULL; *Ahead = (*Ahead)->next; *Dhead = (*Dhead)->next; } int main() { Node* head = newNode(1); head->next = newNode(9); head->next->next = newNode(5); head->next->next->next = newNode(8); head->next->next->next->next = newNode(7); cout << "Input linked list" << endl; printlist(head); sort(&head); cout << "Final Sorted Linked List " << endl; printlist(head); return 0; }

#include <bits stdc++.h="">
using namespace std;

// Linked list node
struct Node {
   int data;
   struct Node* next;
};

Node* mergelist(Node* head1, Node* head2);
void splitList(Node* head, Node** Ahead, Node** Dhead);
void reverselist(Node*& head);

// the function that sorts the
// linked list
void sort(Node** head){
   // Split the linked list into lists
   Node *Ahead, *Dhead;
   splitList(*head, &Ahead, &Dhead);

   // Reverse the descending ordered linked list into ascending order
   reverselist(Dhead);

   // Merge both linked lists 
   *head = mergelist(Ahead, Dhead);
}

// A function to create a new node
Node* newNode(int data)
{
   Node* temp = new Node;
   temp->data = data;
   temp->next = NULL;
   return temp;
}

// function to reverse a linked list
void reverselist(Node*& head){
   Node *prev = NULL, *curr = head, *next;
   while (curr) {
      next = curr->next;
      curr->next = prev;
      prev = curr;
      curr = next;
   }
   head = prev;
}

// function to print a linked list
void printlist(Node* head){
   while (head != NULL) {
      cout << head->data << " ";
      head = head->next;
   }
   cout << endl;
}

// A function to merge two sorted linked lists
Node* mergelist(Node* head1, Node* head2)
{
   // Base cases
   if (!head1)
      return head2;
   if (!head2)
      return head1;

   Node* temp = NULL;
   if (head1->data < head2->data) {
      temp = head1;
      head1->next = mergelist(head1->next, head2);
   }
   else {
      temp = head2;
      head2->next = mergelist(head1, head2->next);
   }
   return temp;
}

// This function alternatively splits
// a linked list into two lists.
// "Ahead" is pointer to head of ascending linked list
// "Dhead" is pointer to head of descending linked list
void splitList(Node* head, Node** Ahead, Node** Dhead){
   // Create two dummy nodes to initialize
   // heads of two linked list
   *Ahead = newNode(0);
   *Dhead = newNode(0);

   Node* ascn = *Ahead;
   Node* dscn = *Dhead;
   Node* curr = head;

   // Link alternate nodes
   while (curr) {
      // Link alternate nodes of ascending linked list
      ascn->next = curr;
      ascn = ascn->next;
      curr = curr->next;

      // Link alternate nodes of descending linked list
      if (curr) {
         dscn->next = curr;
         dscn = dscn->next;
         curr = curr->next;
      }
   }

   ascn->next = NULL;
   dscn->next = NULL;
   *Ahead = (*Ahead)->next;
   *Dhead = (*Dhead)->next;
}

int main()
{
   Node* head = newNode(1);
   head->next = newNode(9);
   head->next->next = newNode(5);
   head->next->next->next = newNode(8);
   head->next->next->next->next = newNode(7);

   cout << "Input linked list" << endl;
   printlist(head);

   sort(&head);

   cout << "Final Sorted Linked List " << endl;
   printlist(head);

   return 0;
}

class Sort

{

Node head;

class Node

{

int data;

Node next;

Node(int d)

{

data = d;

next = null;

}

Node newNode(int key)

{

return new Node(key);

}

/* This is the main function that sorts

the linked list.*/

void sort()

{

/* Create 2 dummy nodes and initialise as

heads of linked lists */

Node Ahead = new Node(0), Dhead = new Node(0);

// Split the list into lists

splitList(Ahead, Dhead);

Ahead = Ahead.next;

Dhead = Dhead.next;

// reverse the descending list

Dhead = reverseList(Dhead);

// merge the 2 linked lists

head = mergeList(Ahead, Dhead);

}

/* Function to reverse the linked list */

Node reverseList(Node Dhead)

{

Node current = Dhead;

Node prev = null;

Node next;

while (current != null) {

next = current.next;

current.next = prev;

prev = current;

current = next;

}

Dhead = prev;

return Dhead;

}

void printList()

{

Node temp = head;

while (temp != null) {

System.out.print(temp.data + " ");

temp = temp.next;

}

System.out.println();

}

// A utility function to merge two sorted linked lists

Node mergeList(Node head1, Node head2)

{

// Base cases

if (head1 == null)

return head2;

if (head2 == null)

return head1;

Node temp = null;

if (head1.data < head2.data) {

temp = head1;

head1.next = mergeList(head1.next, head2);

}

else {

temp = head2;

head2.next = mergeList(head1, head2.next);

}

return temp;

}

// This function alternatively splits

// a linked list with head as head into two:

// For example, 10->20->30->15->40->7 is

// splitted into 10->30->40

// and 20->15->7

// "Ahead" is reference to head of ascending linked list

// "Dhead" is reference to head of descending linked list

void splitList(Node Ahead, Node Dhead)

{

Node ascn = Ahead;

Node dscn = Dhead;

Node curr = head;

// Link alternate nodes

while (curr != null) {

// Link alternate nodes in ascending order

ascn.next = curr;

ascn = ascn.next;

curr = curr.next;

if (curr != null) {

dscn.next = curr;

dscn = dscn.next;

curr = curr.next;

}

ascn.next = null;

dscn.next = null;

}

/* Driver program to test above functions */

public static void main(String args[])

{

Sort llist = new Sort();

llist.head = llist.newNode(10);

llist.head.next = llist.newNode(40);

llist.head.next.next = llist.newNode(53);

llist.head.next.next.next = llist.newNode(30);

llist.head.next.next.next.next = llist.newNode(67);

llist.head.next.next.next.next.next = llist.newNode(12);

llist.head.next.next.next.next.next.next = llist.newNode(89);

System.out.println("Given linked list");

llist.printList();

llist.sort();

System.out.println("Sorted linked list");

llist.printList();

}

class Sort { Node head; class Node { int data; Node next; Node(int d) { data = d; next = null; } } Node newNode(int key) { return new Node(key); } /* This is the main function that sorts the linked list.*/ void sort() { /* Create 2 dummy nodes and initialise as heads of linked lists */ Node Ahead = new Node(0), Dhead = new Node(0); // Split the list into lists splitList(Ahead, Dhead); Ahead = Ahead.next; Dhead = Dhead.next; // reverse the descending list Dhead = reverseList(Dhead); // merge the 2 linked lists head = mergeList(Ahead, Dhead); } /* Function to reverse the linked list */ Node reverseList(Node Dhead) { Node current = Dhead; Node prev = null; Node next; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } Dhead = prev; return Dhead; } void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } // A utility function to merge two sorted linked lists Node mergeList(Node head1, Node head2) { // Base cases if (head1 == null) return head2; if (head2 == null) return head1; Node temp = null; if (head1.data < head2.data) { temp = head1; head1.next = mergeList(head1.next, head2); } else { temp = head2; head2.next = mergeList(head1, head2.next); } return temp; } // This function alternatively splits // a linked list with head as head into two: // For example, 10->20->30->15->40->7 is // splitted into 10->30->40 // and 20->15->7 // "Ahead" is reference to head of ascending linked list // "Dhead" is reference to head of descending linked list void splitList(Node Ahead, Node Dhead) { Node ascn = Ahead; Node dscn = Dhead; Node curr = head; // Link alternate nodes while (curr != null) { // Link alternate nodes in ascending order ascn.next = curr; ascn = ascn.next; curr = curr.next; if (curr != null) { dscn.next = curr; dscn = dscn.next; curr = curr.next; } } ascn.next = null; dscn.next = null; } /* Driver program to test above functions */ public static void main(String args[]) { Sort llist = new Sort(); llist.head = llist.newNode(10); llist.head.next = llist.newNode(40); llist.head.next.next = llist.newNode(53); llist.head.next.next.next = llist.newNode(30); llist.head.next.next.next.next = llist.newNode(67); llist.head.next.next.next.next.next = llist.newNode(12); llist.head.next.next.next.next.next.next = llist.newNode(89); System.out.println("Given linked list"); llist.printList(); llist.sort(); System.out.println("Sorted linked list"); llist.printList(); } }

class Sort 
{
    Node head; 
    class Node 
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }

    Node newNode(int key)
    {
        return new Node(key);
    }

    /* This is the main function that sorts
    the linked list.*/
    void sort()
    {
        /* Create 2 dummy nodes and initialise as
        heads of linked lists */
        Node Ahead = new Node(0), Dhead = new Node(0);

        // Split the list into lists
        splitList(Ahead, Dhead);

        Ahead = Ahead.next;
        Dhead = Dhead.next;

        // reverse the descending list
        Dhead = reverseList(Dhead);

        // merge the 2 linked lists
        head = mergeList(Ahead, Dhead);
    }

    /* Function to reverse the linked list */
    Node reverseList(Node Dhead)
    {
        Node current = Dhead;
        Node prev = null;
        Node next;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        Dhead = prev;
        return Dhead;
    }
    void printList()
    {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println();
    }
    // A utility function to merge two sorted linked lists
    Node mergeList(Node head1, Node head2)
    {
        // Base cases
        if (head1 == null)
            return head2;
        if (head2 == null)
            return head1;

        Node temp = null;
        if (head1.data < head2.data) {
            temp = head1;
            head1.next = mergeList(head1.next, head2);
        }
        else {
            temp = head2;
            head2.next = mergeList(head1, head2.next);
        }
        return temp;
    }

    // This function alternatively splits
    // a linked list with head as head into two:
    // For example, 10->20->30->15->40->7 is
    // splitted into 10->30->40
    // and 20->15->7
    // "Ahead" is reference to head of ascending linked list
    // "Dhead" is reference to head of descending linked list
    void splitList(Node Ahead, Node Dhead)
    {
        Node ascn = Ahead;
        Node dscn = Dhead;
        Node curr = head;

        // Link alternate nodes

        while (curr != null) {
            // Link alternate nodes in ascending order
            ascn.next = curr;
            ascn = ascn.next;
            curr = curr.next;

            if (curr != null) {
                dscn.next = curr;
                dscn = dscn.next;
                curr = curr.next;
            }
        }

        ascn.next = null;
        dscn.next = null;
    }

    /* Driver program to test above functions */
    public static void main(String args[])
    {
        Sort llist = new Sort();
        llist.head = llist.newNode(10);
        llist.head.next = llist.newNode(40);
        llist.head.next.next = llist.newNode(53);
        llist.head.next.next.next = llist.newNode(30);
        llist.head.next.next.next.next = llist.newNode(67);
        llist.head.next.next.next.next.next = llist.newNode(12);
        llist.head.next.next.next.next.next.next = llist.newNode(89);

        System.out.println("Given linked list");
        llist.printList();

        llist.sort();

        System.out.println("Sorted linked list");
        llist.printList();
    }

}

class LinkedList(object):

def __init__(self):

self.head = None

# Linked list Node

class Node(object):

def __init__(self, d):

self.data = d

self.next = None

def newNode(self, key):

return self.Node(key)

# This is the main function that sorts

# the linked list.

def sort(self):

# Create 2 dummy nodes and initialise as

# heads of linked lists

Ahead = self.Node(0)

Dhead = self.Node(0)

# Split the list into lists

self.splitList(Ahead, Dhead)

Ahead = Ahead.next

Dhead = Dhead.next

# reverse the descending list

Dhead = self.reverseList(Dhead)

# merge the 2 linked lists

self.head = self.mergeList(Ahead, Dhead)

# Function to reverse the linked list

def reverseList(self, Dhead):

current = Dhead

prev = None

while current != None:

self._next = current.next

current.next = prev

prev = current

current = self._next

Dhead = prev

return Dhead

# Function to print linked list

def printList(self):

temp = self.head

while temp != None:

print (temp.data,end=" ")

temp = temp.next

print()

# A utility function to merge two sorted linked lists

def mergeList(self, head1, head2):

# Base cases

if head1 == None:

return head2

if head2 == None:

return head1

temp = None

if head1.data < head2.data:

temp = head1

head1.next = self.mergeList(head1.next, head2)

else:

temp = head2

head2.next = self.mergeList(head1, head2.next)

return temp

# This function alternatively splits a linked list with head

# as head into two:

# "Ahead" is reference to head of ascending linked list

# "Dhead" is reference to head of descending linked list

def splitList(self, Ahead, Dhead):

ascn = Ahead

dscn = Dhead

curr = self.head

# Link alternate nodes

while curr != None:

# Link alternate nodes in ascending order

ascn.next = curr

ascn = ascn.next

curr = curr.next

if curr != None:

dscn.next = curr

dscn = dscn.next

curr = curr.next

ascn.next = None

dscn.next = None

llist = LinkedList()

llist.head = llist.newNode(1)

llist.head.next = llist.newNode(9)

llist.head.next.next = llist.newNode(5)

llist.head.next.next.next = llist.newNode(8)

llist.head.next.next.next.next = llist.newNode(7)

print ('Given linked list')

llist.printList()

llist.sort()

print ('Sorted linked list')

llist.printList()

class LinkedList(object): def __init__(self): self.head = None # Linked list Node class Node(object): def __init__(self, d): self.data = d self.next = None def newNode(self, key): return self.Node(key) # This is the main function that sorts # the linked list. def sort(self): # Create 2 dummy nodes and initialise as # heads of linked lists Ahead = self.Node(0) Dhead = self.Node(0) # Split the list into lists self.splitList(Ahead, Dhead) Ahead = Ahead.next Dhead = Dhead.next # reverse the descending list Dhead = self.reverseList(Dhead) # merge the 2 linked lists self.head = self.mergeList(Ahead, Dhead) # Function to reverse the linked list def reverseList(self, Dhead): current = Dhead prev = None while current != None: self._next = current.next current.next = prev prev = current current = self._next Dhead = prev return Dhead # Function to print linked list def printList(self): temp = self.head while temp != None: print (temp.data,end=" ") temp = temp.next print() # A utility function to merge two sorted linked lists def mergeList(self, head1, head2): # Base cases if head1 == None: return head2 if head2 == None: return head1 temp = None if head1.data < head2.data: temp = head1 head1.next = self.mergeList(head1.next, head2) else: temp = head2 head2.next = self.mergeList(head1, head2.next) return temp # This function alternatively splits a linked list with head # as head into two: # "Ahead" is reference to head of ascending linked list # "Dhead" is reference to head of descending linked list def splitList(self, Ahead, Dhead): ascn = Ahead dscn = Dhead curr = self.head # Link alternate nodes while curr != None: # Link alternate nodes in ascending order ascn.next = curr ascn = ascn.next curr = curr.next if curr != None: dscn.next = curr dscn = dscn.next curr = curr.next ascn.next = None dscn.next = None llist = LinkedList() llist.head = llist.newNode(1) llist.head.next = llist.newNode(9) llist.head.next.next = llist.newNode(5) llist.head.next.next.next = llist.newNode(8) llist.head.next.next.next.next = llist.newNode(7) print ('Given linked list') llist.printList() llist.sort() print ('Sorted linked list') llist.printList()

class LinkedList(object):
    def __init__(self):
        self.head = None

    # Linked list Node
    class Node(object):
        def __init__(self, d):
            self.data = d
            self.next = None

    def newNode(self, key):
        return self.Node(key)

    # This is the main function that sorts
    # the linked list.
    def sort(self):
        # Create 2 dummy nodes and initialise as
        # heads of linked lists
        Ahead = self.Node(0)
        Dhead = self.Node(0)
        # Split the list into lists
        self.splitList(Ahead, Dhead)
        Ahead = Ahead.next
        Dhead = Dhead.next
        # reverse the descending list
        Dhead = self.reverseList(Dhead)
        # merge the 2 linked lists
        self.head = self.mergeList(Ahead, Dhead)

    # Function to reverse the linked list
    def reverseList(self, Dhead):
        current = Dhead
        prev = None
        while current != None:
            self._next = current.next
            current.next = prev
            prev = current
            current = self._next
        Dhead = prev
        return Dhead

    # Function to print linked list
    def printList(self):
        temp = self.head
        while temp != None:
            print (temp.data,end=" ")
            temp = temp.next
        print()

    # A utility function to merge two sorted linked lists
    def mergeList(self, head1, head2):
        # Base cases
        if head1 == None:
            return head2
        if head2 == None:
            return head1
        temp = None
        if head1.data < head2.data:
            temp = head1
            head1.next = self.mergeList(head1.next, head2)
        else:
            temp = head2
            head2.next = self.mergeList(head1, head2.next)
        return temp

    # This function alternatively splits a linked list with head
    # as head into two:
    # "Ahead" is reference to head of ascending linked list
    # "Dhead" is reference to head of descending linked list
    def splitList(self, Ahead, Dhead):
        ascn = Ahead
        dscn = Dhead
        curr = self.head
        # Link alternate nodes
        while curr != None:
            # Link alternate nodes in ascending order
            ascn.next = curr
            ascn = ascn.next
            curr = curr.next
            if curr != None:
                dscn.next = curr
                dscn = dscn.next
                curr = curr.next
        ascn.next = None
        dscn.next = None

llist = LinkedList()
llist.head = llist.newNode(1)
llist.head.next = llist.newNode(9)
llist.head.next.next = llist.newNode(5)
llist.head.next.next.next = llist.newNode(8)
llist.head.next.next.next.next = llist.newNode(7)

print ('Given linked list')
llist.printList()

llist.sort()

print ('Sorted linked list')
llist.printList()

Output

Input Linked list:
1 9 5 8 7
Final Sorted Linked List:
1 5 7 8 9

Time Complexity: O(n), We have traversed through the linked list only once to separate the list and reverse the list. The merging of two sorted lists into a single linked list takes O(n) time.

Auxiliary Space: O(1), No extra space is required.

So, In this blog, we have learned to sort a linked list that is sorted alternating ascending and descending orders. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

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

Introduction

Problem Statement

Problem Statement Understanding

Approach

Algorithm

Code Implementation

Output

Leave a Reply Cancel reply

Integrated Services Digital Network (ISDN)

VLAN ACL (VACL) in Computer Networks

Inter-VLAN Routing Using a Layer 3 Switch

Access and Trunk Ports in Computer Networks

Role-Based Access Control (RBAC) in Computer Networks

Display Processor in Computer Graphics

Sign in to your account

Login via OTP

Login via OTP

Register with PrepBytes

Introduction

Problem Statement

Problem Statement Understanding

Approach

Algorithm

Code Implementation

Output

Leave a Reply Cancel reply