Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example  
4.
Intuition 
5.
Code
5.1.
Output: 
6.
Complexity Analysis
6.1.
Time Complexity
6.2.
Space Complexity
7.
Frequently Asked Questions
7.1.
How is the linked list represented in memory?
7.2.
How is the linked list different from the array?
7.3.
How do we check for palindromes in a linked list?
7.4.
Are linked lists (FIFO) or (LIFO)?
7.5.
Why are linked lists used over arrays?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Sort Linked List which is already sorted on absolute values

Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

One of the most crucial things to understand while preparing for technical interviews is Data Structures and Algorithms, questions related to linked lists are frequently asked in all the companies. Knowing how to use a linked list effectively may be quite beneficial in coding interviews. A linked list is a linear collection of data components whose order is determined by their physical location in memory rather than by their physical order. Instead, each piece serves as a stepping stone to the next. It's a data structure made up of a number of nodes that together form a sequence.

Recommended Topic, Floyds Algorithm

Problem Statement

Sort a linked list based on real values given a linked list sorted by absolute values. You will be given a linked list in which node values are sorted based on their absolute values (for example, the absolute value of -9 is 9). 

Example  

Let's take an example to understand more about absolute sorted Linked List.

Absolute Sorted Linked List : 1 2 -3 4 -5 6 7 -8

Note that in the above example though -3 < 2, still in the increasing order sequence -3 is placed after 2 because the absolute value of -3 is 3 which is greater than 2. Same goes for -5 and -8 as well.

The Sorted Linked List will be 
 : -8 -5 -3 1 2 4 6 7   

Recommended: Its highly recommended to solve this problem on your own on Coding Ninjas Studio before moving on to the Solution.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Intuition 

An easy method is to go from the beginning to the end of the linked list. Examine each node you've visited to see whether it's out of sequence. If this is the case, delete it from its present location and replace it with the proper location. This is very similar to what we used to do when sorting an array using insertion sort. The time complexity of this approach is O(n*n), and it implements insertion sort for a linked list.

Original Linked List : 1 2 -3 4 -5 6 7 -8
Sorted Linked List : -8 -5 -3 1 2 4 6 7  

From the above example, you can clearly see that the positive numbers will be placed in the proper sequence and the negative values are already sorted in a reversed way.  
A better method is to use merge sort to sort the linked list. This solution has a time complexity of O(n Log n). 
In O(n) time, an efficient solution may be implemented. All negative components are present in reverse order, which is a significant discovery. As we go through the list, we move any elements that are out of order to the head of the linked list. 
Let’s look at how we can implement this solution.

Must Read Difference between ArrayList and LinkedList

Code

#include <bits/stdc++.h>
using namespace std;
 
struct Node
{
    Node* next;
    int val;
};
 
// Function to print a linked list
void printLinkedList(Node* head)
{
    while (head != NULL)
    {
        cout << head->val;
        if (head->next != NULL){
            cout << " ";
        }
        head = head->next;
    }
    cout<<endl;
}
 
void sortLinkedList(Node** head)
{
    Node* prev = (*head);
    Node* curr = (*head)->next;
 
    // Traverse list
    while (curr != NULL)
    {
        if (curr->val < prev->val)
        {
            prev->next = curr->next;
 
            curr->next = (*head);
            (*head) = curr;
            
            curr = prev;
        }
        else
            prev = curr;
 
        curr = curr->next;
    }
}

// Function to insert a node at start
void addNode(Node** head, int val)
{
    Node* newNode = new Node;
    newNode->next = (*head);
    newNode->val = val;
    (*head) = newNode;
}
 
 
int main()
{
    Node* head = NULL;
    addNode(&head, -8);
    addNode(&head, 7);
    addNode(&head, 6);
    addNode(&head, -5);
    addNode(&head, 4);
    addNode(&head, -3);
    addNode(&head, 2);
    addNode(&head, 1);
 
    cout << "Original list : "<<endl;
    
    printLinkedList(head);
 
    sortLinkedList(&head);
 
    cout << "\nSorted list :"<<endl;
    
    printLinkedList(head);
 
    return 0;
}

Output: 

Original list :  
1 2 -3 4 -5 6 7 -8

Sorted list : 
-8 -5 -3 1 2 4 6 7

Also read - Merge sort in linked list

Complexity Analysis

Time Complexity

We need to traverse the n-sized linked list only once. Thus, the time complexity of the program is O(n).

Space Complexity

O(1)

Frequently Asked Questions

How is the linked list represented in memory?

The linked list is kept in memory in a scattered way (locations). Each node's memory is allocated dynamically, that is, as and when it is needed. As a result, the linked list may grow as the user desires, and the size is not fixed; it can change.

How is the linked list different from the array?

An array is a grouping of items of the same data type. A linked list is an ordered collection of elements of the same type with pointers connecting each element to the next.

How do we check for palindromes in a linked list?

Traverse the linked list and save all of the linked list's elements in that string.

Examine the linked list to see if the first and last characters are equivalent. This will not make a palindrome if they are not equal at some point.

Are linked lists (FIFO) or (LIFO)?

The LinkedList class implements the List, Deque, and Queue interfaces. The first-in, first-out (FIFO) principle governs how a queue stores and removes its components. LinkedList may be used to represent a first-in, first-out (FIFO) queue since it implements the Deque interface.

Why are linked lists used over arrays?

Linked lists are more efficient than arrays in terms of memory allocation. Unlike arrays, the size of a linked list is not fixed, so it can grow or shrink as the program runs.

Conclusion

In this article, we discussed the problem related to sorting a linked list that is already sorted on absolute values. We hope that this blog has helped you enhance your problem-solving skills, and if you would like to learn more, check out our Linked List and Application of Linked List articles on Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!

 

 

Previous article
Alternate Odd and Even Nodes in a Singly Linked List
Next article
How to Swap Kth Node from the Beginning with Kth Node from the End in the given Singly Linked List
Live masterclass