  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

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

struct Node {
int data;
struct Node* next;
};

// the function that sorts the
// Split the linked list into lists

// Reverse the descending ordered linked list into ascending order

}

// 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
Node *prev = NULL, *curr = head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
}

// function to print a linked list
cout << head->data << " ";
}
cout << endl;
}

// A function to merge two sorted linked lists
{
// Base cases

Node* temp = NULL;
}
else {
}
return temp;
}

// This function alternatively splits
// a linked list into two lists.
// Create two dummy nodes to initialize

while (curr) {
ascn->next = curr;
ascn = ascn->next;
curr = curr->next;

if (curr) {
dscn->next = curr;
dscn = dscn->next;
curr = curr->next;
}
}

ascn->next = NULL;
dscn->next = NULL;
}

int main()
{

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

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

return 0;
}
```
```class Sort
{
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
void sort()
{
/* Create 2 dummy nodes and initialise as

// Split the list into lists

// reverse the descending list

// merge the 2 linked lists
}

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

Node temp = null;
}
else {
}
return temp;
}

// This function alternatively splits
// For example, 10->20->30->15->40->7 is
// splitted into 10->30->40
// and 20->15->7
{

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.printList();

llist.sort();

llist.printList();
}

}
```
```class LinkedList(object):
def __init__(self):

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
def sort(self):
# Create 2 dummy nodes and initialise as
# Split the list into lists
# reverse the descending list
# merge the 2 linked lists

# Function to reverse the linked list
prev = None
while current != None:
self._next = current.next
current.next = prev
prev = current
current = self._next

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

# A utility function to merge two sorted linked lists
# Base cases
temp = None
else:
return temp

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.printList()

llist.sort()

llist.printList()
```