Sort LL
Linked-List
FAQs (Hard)
Hard
- Fun Fact: Sorting a list is one of the most common operations in software development
- In real-world applications, the concept of sorting a linked list in a non-decreasing order is extensively used in contact lists apps
- For instance, when you look up your contacts in any messenger app or social media platform, names are typically displayed in alphabetically sorted order, which is a non-decreasing order
- Behind the scenes, this concept is implemented in their software’s architecture for managing and displaying contacts!
Given the head of a singly linked list. Sort the values of the linked list in non-decreasing order and return the head of the modified linked list.
Examples:
Input: head -> 5 -> 6 -> 1 -> 2 -> 1
Output: head -> 1 -> 1 -> 2 -> 5 -> 6
Explanation: 1 <= 1 <= 2 <= 5 <= 6
Input: head -> 6 -> 5 -> -1 -> -2 -> -3
Output: head -> -3 -> -2 -> -1 -> 5 -> 6
Explanation: -3 <= -2 <= -1 <= 5 <= 6
Input: head -> -1 -> -2 -> -3 -> -1
Constraints
- 0 <= number of nodes in the linked list <= 1000
- -104 <= ListNode.val <= 104
Hints
- Before merging, we check each child linked list for cycles using Floyd’s Cycle Detection Algorithm. Find the Start of the Cycle and Break the Cycle.
- Use a Min-Heap (O(N log k)) or Divide & Conquer (O(N log k)) to merge the sorted lists. Return the flattened sorted list.
Company Tags
MongoDB
Optum
Mastercard
PwC
Docker
Reddit
Epic Systems
Etsy
Siemens Healthineers
Broadcom
Flipkart
GE Healthcare
HashiCorp
OYO Rooms
Byju's
Bungie
American Express
Alibaba
eBay
Philips Healthcare
McKinsey & Company
Micron Technology
Seagate Technology
AMD
ARM
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Intuition
A straightforward approach to sorting a linked list involves converting the linked list into an array. Once converted, the array can be sorted using any standard sorting algorithm. After sorting, a new linked list can be created using the sorted values from the array.
Approach
- Create an empty array to store the node values.
- Traverse the linked list using a temporary pointer starting at the head, pushing each node's value into the array, and moving the pointer to the next node.
- Sort the array containing the node values in ascending order.
- Convert the sorted array back into a linked list by reassigning the values from the sorted array to the nodes, overwriting the values sequentially according to the order in the array.
Dry Run
Solution
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
#include <bits/stdc++.h>
using namespace std;
// Definition of singly linked list
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int data1) : val(data1), next(NULL) {}
ListNode(int data1, ListNode *next1) : val(data1), next(next1) {}
};
class Solution {
public:
// Function to sort Linked List
ListNode* sortList(ListNode* head) {
// Vector to store node values
vector<int> arr;
/*Temporary pointer to
traverse the linked list*/
ListNode* temp = head;
/* Traverse the linked list and
store node values in the vector*/
while(temp != NULL) {
arr.push_back(temp->val);
temp = temp->next;
}
// Sort array containing node values
sort(arr.begin(), arr.end());
// Reassign sorted values to linked list nodes
temp = head;
for(int i = 0; i < arr.size(); i++) {
// Update the node's data
temp->val = arr[i];
// Move to the next node
temp = temp->next;
}
// Return the head
return head;
}
};
// Function to print the linked list
void printLinkedList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
// Print the data of the current node
cout << temp->val << " ";
// Move to the next node
temp = temp->next;
}
cout << endl;
}
int main() {
// Linked List: 3 2 5 4 1
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(5);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(1);
cout << "Original Linked List: ";
printLinkedList(head);
Solution solution;
// Sort the linked list
head = solution.sortList(head);
cout << "Sorted Linked List: ";
printLinkedList(head);
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990
import java.util.*;
// Definition of singly linked list
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int val) {
this.val = val;
this.next = null;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to sort Linked List
public ListNode sortList(ListNode head) {
// ArrayList to store node values
List<Integer> arr = new ArrayList<>();
// Temporary pointer to traverse the linked list
ListNode temp = head;
/*Traverse linked list and
store node values in the ArrayList*/
while (temp != null) {
arr.add(temp.val);
temp = temp.next;
}
// Sort ArrayList containing node values
Collections.sort(arr);
/*Reassign sorted values
to linked list nodes*/
temp = head;
for (int val : arr) {
// Update the node's data
temp.val = val;
// Move to the next node
temp = temp.next;
}
// Return the head
return head;
}
}
// Function to print the linked list
public class Main {
public static void printLinkedList(ListNode head) {
ListNode temp = head;
while (temp != null) {
// Print the data of the current node
System.out.print(temp.val + " ");
// Move to the next node
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
// Linked List: 3 2 5 4 1
ListNode head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(5);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(1);
System.out.print("Original Linked List: ");
printLinkedList(head);
Solution solution = new Solution();
// Sort the linked list
head = solution.sortList(head);
System.out.print("Sorted Linked List: ");
printLinkedList(head);
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to sort Linked List
def sortList(self, head):
# List to store node values
arr = []
# Temporary pointer to traverse
# the linked list
temp = head
# Traverse the linked list
while temp:
arr.append(temp.val)
temp = temp.next
# Sort list containing node values
arr.sort()
# Reassign sorted values to
# linked list nodes
temp = head
for val in arr:
# Update the node's data
temp.val = val
# Move to the next node
temp = temp.next
# Return the head
return head
# Function to print the linked list
def printLinkedList(head):
temp = head
while temp:
# Print the data of the current node
print(temp.val, end=" ")
# Move to the next node
temp = temp.next
print()
# Linked List: 3 2 5 4 1
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(5)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(1)
print("Original Linked List: ", end="")
printLinkedList(head)
solution = Solution()
# Sort the linked list
head = solution.sortList(head)
print("Sorted Linked List: ", end="")
printLinkedList(head)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to sort Linked List
sortList(head) {
// Array to store node values
let arr = [];
/*Temporary pointer to
traverse the linked list*/
let temp = head;
/* Traverse the linked list and
store node values in the array*/
while (temp !== null) {
arr.push(temp.val);
temp = temp.next;
}
// Sort array containing node values
arr.sort((a, b) => a - b);
// Reassign sorted values to linked list nodes
temp = head;
for (let i = 0; i < arr.length; i++) {
// Update the node's data
temp.val = arr[i];
// Move to the next node
temp = temp.next;
}
// Return the head
return head;
}
}
// Function to print the linked list
function printLinkedList(head) {
let temp = head;
while (temp !== null) {
// Print the data of the current node
process.stdout.write(temp.val + " ");
// Move to the next node
temp = temp.next;
}
console.log();
}
// Linked List: 3 2 5 4 1
let head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(5);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(1);
console.log("Original Linked List: ");
printLinkedList(head);
let solution = new Solution();
// Sort the linked list
head = solution.sortList(head);
console.log("Sorted Linked List: ");
printLinkedList(head);
Complexity Analysis
Time Complexity: O(N) + O(N log N) + O(N) for the following reasons:-
- O(N): Time taken to traverse the linked list and store its data values in an array.
- O(N log N): Time taken to sort the array of node values.
- O(N): Time taken to traverse the sorted array and reassign values back to the linked list.
Here N represents the number of nodes in the linked list.
Space Complexity: O(N) because we need to store values of nodes of the linked lists in the array of size N where N is the length of the linked list.
Intuition
Instead of using an external array to store node values, we can utilize an in-place sorting algorithm such as Merge Sort or Quick Sort, which can be adapted for linked lists. This approach avoids using additional space. Merge Sort employs the divide and conquer strategy:-- Divides the linked list into smaller parts until they become trivial to sort (single node or empty list).
- Merges and sorts the divided parts while combining them back together.
Approach
- Base Case: If the linked list contains zero or one element, it is already sorted. Return the head node.
- Split the List: Find the middle of the linked list using a slow and a fast pointer. Split the linked list into two halves at the middle node. The two halves will be left and right.
- Recursion: Recursively apply merge sort to both halves obtained in the previous step. This step continues dividing the linked list until there's only one node in each half.
- Merge Sorted Lists: Merge the sorted halves obtained from the recursive calls into a single sorted linked list. Compare the nodes from both halves and rearrange them to form a single sorted list. Update the head pointer to the beginning of the newly sorted list.
- Return: Once the merging is complete, return the head of the sorted linked list.
Dry Run
Breaking down the list and then sorting the smaller parts
Solution
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132
#include <bits/stdc++.h>
using namespace std;
// Definition of singly linked list
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int data1) : val(data1), next(NULL) {}
ListNode(int data1, ListNode *next1) : val(data1), next(next1) {}
};
class Solution {
public:
// Function to merge two sorted linked lists
ListNode* mergeTwoSortedLinkedLists(ListNode* list1, ListNode* list2) {
// Create dummy node to serve as head of merged list
ListNode* dummyNode = new ListNode(-1);
ListNode* temp = dummyNode;
// Traverse both lists simultaneously
while (list1 != nullptr && list2 != nullptr) {
/*Compare elements of both lists
and link the smaller node
to the merged list*/
if (list1->val <= list2->val) {
temp->next = list1;
list1 = list1->next;
} else {
temp->next = list2;
list2 = list2->next;
}
// Move the temporary pointer to the next node
temp = temp->next;
}
/*If any list still has
remaining elements append
them to the merged list*/
if (list1 != nullptr) {
temp->next = list1;
} else {
temp->next = list2;
}
// Return the merged list starting
// from the next of the dummy node
return dummyNode->next;
}
// Function to find the middle of a linked list
ListNode* findMiddle(ListNode* head) {
// If the list is empty or has only one node,
// the middle is the head itself
if (head == nullptr || head->next == nullptr) {
return head;
}
// Initializing slow and fast pointers
ListNode* slow = head;
ListNode* fast = head->next;
/* Move the fast pointer twice as fast as the slow pointer
When the fast pointer reaches the end, the slow pointer
will be at the middle*/
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// Function to perform merge sort on a linked list
ListNode* sortList(ListNode* head) {
/*Base case: if the list is empty or has only one node,
it is already sorted, so return the head*/
if (head == nullptr || head->next == nullptr) {
return head;
}
// Find middle of list using findMiddle function
ListNode* middle = findMiddle(head);
// Divide the list into two halves
ListNode* right = middle->next;
middle->next = nullptr;
ListNode* left = head;
// Recursively sort left and right halves
left = sortList(left);
right = sortList(right);
// Merge the sorted halves using the
// mergeTwoSortedLinkedLists function
return mergeTwoSortedLinkedLists(left, right);
}
};
// Function to print the linked list
void printLinkedList(ListNode* head) {
ListNode* temp = head;
while (temp != nullptr) {
// Print the data of the current node
cout << temp->val << " ";
// Move to the next node
temp = temp->next;
}
cout << endl;
}
int main() {
// Linked List: 3 2 5 4 1
ListNode* head = new ListNode(3);
head->next = new ListNode(2);
head->next->next = new ListNode(5);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(1);
cout << "Original Linked List: ";
printLinkedList(head);
Solution solution;
// Sort the linked list
head = solution.sortList(head);
cout << "Sorted Linked List: ";
printLinkedList(head);
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140
import java.util.*;
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int val) {
this.val = val;
this.next = null;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to merge two sorted linked lists
public ListNode mergeTwoSortedLinkedLists(ListNode list1, ListNode list2) {
// Create dummy node to serve as head of merged list
ListNode dummyNode = new ListNode(-1);
ListNode temp = dummyNode;
// Traverse both lists simultaneously
while (list1 != null && list2 != null) {
/*Compare elements of both lists
and link the smaller node
to the merged list*/
if (list1.val <= list2.val) {
temp.next = list1;
list1 = list1.next;
} else {
temp.next = list2;
list2 = list2.next;
}
// Move the temporary pointer to the next node
temp = temp.next;
}
/*If any list still has
remaining elements append
them to the merged list*/
if (list1 != null) {
temp.next = list1;
} else {
temp.next = list2;
}
// Return the merged list starting
// from the next of the dummy node
return dummyNode.next;
}
// Function to find the middle of a linked list
public ListNode findMiddle(ListNode head) {
// If the list is empty or has only one node,
// the middle is the head itself
if (head == null || head.next == null) {
return head;
}
// Initializing slow and fast pointers
ListNode slow = head;
ListNode fast = head.next;
/* Move the fast pointer twice as fast as the slow pointer
When the fast pointer reaches the end, the slow pointer
will be at the middle*/
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// Function to perform merge sort on a linked list
public ListNode sortList(ListNode head) {
/*Base case: if the list is empty or has only one node,
it is already sorted, so return the head*/
if (head == null || head.next == null) {
return head;
}
// Find middle of list using findMiddle function
ListNode middle = findMiddle(head);
// Divide the list into two halves
ListNode right = middle.next;
middle.next = null;
ListNode left = head;
// Recursively sort left and right halves
left = sortList(left);
right = sortList(right);
// Merge the sorted halves using the
// mergeTwoSortedLinkedLists function
return mergeTwoSortedLinkedLists(left, right);
}
}
// Function to print the linked list
public class Main {
public static void printLinkedList(ListNode head) {
ListNode temp = head;
while (temp != null) {
// Print the data of the current node
System.out.print(temp.val + " ");
// Move to the next node
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
// Linked List: 3 2 5 4 1
ListNode head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(5);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(1);
System.out.print("Original Linked List: ");
printLinkedList(head);
Solution solution = new Solution();
// Sort the linked list
head = solution.sortList(head);
System.out.print("Sorted Linked List: ");
printLinkedList(head);
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
class ListNode:
def _init_(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to merge two sorted linked lists
def mergeTwoSortedLinkedLists(self, list1, list2):
# Create dummy node to serve as head of merged list
dummyNode = ListNode(-1)
temp = dummyNode
# Traverse both lists simultaneously
while list1 is not None and list2 is not None:
# Compare elements of both lists and link the smaller node to the merged list
if list1.val <= list2.val:
temp.next = list1
list1 = list1.next
else:
temp.next = list2
list2 = list2.next
# Move the temporary pointer to the next node
temp = temp.next
# If any list still has remaining elements, append them to the merged list
if list1 is not None:
temp.next = list1
else:
temp.next = list2
# Return the merged list starting from the next of the dummy node
return dummyNode.next
# Function to find the middle of a linked list
def findMiddle(self, head):
# If the list is empty or has only one node, the middle is the head itself
if head is None or head.next is None:
return head
# Initializing slow and fast pointers
slow = head
fast = head.next
# Move the fast pointer twice as fast as the slow pointer
# When the fast pointer reaches the end, the slow pointer will be at the middle
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
return slow
# Function to perform merge sort on a linked list
def sortList(self, head):
# Base case: if the list is empty or has only one node, it is already sorted, so return the head
if head is None or head.next is None:
return head
# Find middle of list using findMiddle function
middle = self.findMiddle(head)
# Divide the list into two halves
right = middle.next
middle.next = None
left = head
# Recursively sort left and right halves
left = self.sortList(left)
right = self.sortList(right)
# Merge the sorted halves using the mergeTwoSortedLinkedLists function
return self.mergeTwoSortedLinkedLists(left, right)
# Function to print the linked list
def printLinkedList(head):
temp = head
while temp is not None:
# Print the data of the current node
print(temp.val, end=" ")
# Move to the next node
temp = temp.next
print()
if _name_ == "_main_":
# Linked List: 3 2 5 4 1
head = ListNode(3)
head.next = ListNode(2)
head.next.next = ListNode(5)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(1)
print("Original Linked List: ", end="")
printLinkedList(head)
solution = Solution()
# Sort the linked list
head = solution.sortList(head)
print("Sorted Linked List: ", end="")
printLinkedList(head)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to merge two sorted linked lists
mergeTwoSortedLinkedLists(list1, list2) {
// Create dummy node to serve as head of merged list
let dummyNode = new ListNode(-1);
let temp = dummyNode;
// Traverse both lists simultaneously
while (list1 !== null && list2 !== null) {
/*Compare elements of both lists
and link the smaller node
to the merged list*/
if (list1.val <= list2.val) {
temp.next = list1;
list1 = list1.next;
} else {
temp.next = list2;
list2 = list2.next;
}
// Move the temporary pointer to the next node
temp = temp.next;
}
/*If any list still has
remaining elements append
them to the merged list*/
if (list1 !== null) {
temp.next = list1;
} else {
temp.next = list2;
}
// Return the merged list starting
// from the next of the dummy node
return dummyNode.next;
}
// Function to find the middle of a linked list
findMiddle(head) {
// If the list is empty or has only one node,
// the middle is the head itself
if (head === null || head.next === null) {
return head;
}
// Initializing slow and fast pointers
let slow = head;
let fast = head.next;
/* Move the fast pointer twice as fast as the slow pointer
When the fast pointer reaches the end, the slow pointer
will be at the middle*/
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// Function to perform merge sort on a linked list
sortList(head) {
/*Base case: if the list is empty or has only one node,
it is already sorted, so return the head*/
if (head === null || head.next === null) {
return head;
}
// Find middle of list using findMiddle function
let middle = this.findMiddle(head);
// Divide the list into two halves
let right = middle.next;
middle.next = null;
let left = head;
// Recursively sort left and right halves
left = this.sortList(left);
right = this.sortList(right);
// Merge the sorted halves using the
// mergeTwoSortedLinkedLists function
return this.mergeTwoSortedLinkedLists(left, right);
}
}
// Function to print the linked list
function printLinkedList(head) {
let temp = head;
while (temp !== null) {
// Print the data of the current node
process.stdout.write(temp.val + " ");
// Move to the next node
temp = temp.next;
}
console.log();
}
// Linked List: 3 2 5 4 1
let head = new ListNode(3);
head.next = new ListNode(2);
head.next.next = new ListNode(5);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(1);
console.log("Original Linked List: ");
printLinkedList(head);
let solution = new Solution();
// Sort the linked list
head = solution.sortList(head);
console.log("Sorted Linked List: ");
printLinkedList(head);
Complexity Analysis
Time Complexity: O(N log N) where N is the number of nodes in the linked list. Finding the middle node of the linked list requires traversing it linearly taking O(N) time complexity and to reach the individual nodes of the list, it has to be split log N times (continuously halve the list until we have individual elements).
Space Complexity: O(1) as no additional data structures or space is allocated for storage during the merging process. However, space proportional to O(log N) stack space is required for the recursive calls. The maximum recursion depth of log N height is occupied on the call stack.
Frequently Occurring Doubts
Q: Why do we need to check for cycles before merging?
A: If a cycle exists, the merging process enters an infinite loop, preventing termination.
Q: Can we remove cycles after merging instead?
A: No, because merging assumes that lists are finite. If cycles exist, merging would never terminate.
Interview Followup Questions
Q: What if a cycle exists in the final merged list instead of the child lists?
A: The same Floyd’s Cycle Detection Algorithm can be applied after merging to check for cycles.
Q: Can we optimize cycle detection further?
A: Yes, by maintaining visited node references (O(n) space), but Floyd’s Algorithm is preferred for O(1) space.
Notes
Code
✅ Testcase
Input: {'nums': '[5, 6, 1, 2, 1]'}
Expected:
1 1 2 5 6
1 1 2 5 6
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[6, 5, -1, -2, -3]'}
Expected:
-3 -2 -1 5 6
-3 -2 -1 5 6
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[-1, -2, -3, -1]'}
Expected:
-3 -2 -1 -1
-3 -2 -1 -1
Actual: -
Time: -
sec
Status: Waiting