Sort a Linked List Using Merge Sort

112.1k
0

Given the head of a singly linked list, sort the linked list in non-decreasing order and return the head of the sorted linked list.

Each node contains an integer value and a pointer to the next node. The relative node links may be rearranged, but the final list must contain exactly the same node values in sorted order.

Example 1

Input: head = [4, 2, 1, 3]

Output: [1, 2, 3, 4]

Explanation: Node values are arranged in non-decreasing order.

Example 2

Input: head = [-1, 5, 3, 4, 0]

Output: [-1, 0, 3, 4, 5]

Explanation: Negative, zero, and positive values appear in sorted order.

Brute Force Approach

In this approach, we collect all node values from the linked list into an array. Since arrays can be sorted efficiently, we sort the collected values in non-decreasing order.

After sorting, we traverse the linked list again and overwrite each node's value with the corresponding value from the sorted array. The node connections remain unchanged, and only the values stored in the nodes are updated.

Algorithm

  • Create an empty array to store the values of the linked list, as an array provides a convenient way to collect and sort all node values.

  • Traverse the linked list and append each node's value to the array, so every value is available for sorting.

  • Sort the array in non-decreasing order, as the required linked list should have its values arranged from smallest to largest.

  • Reset the traversal pointer to head, since the sorted values now need to be written back into the existing nodes.

  • Traverse the linked list again and replace each node's value with the corresponding value from the sorted array, which transfers the sorted order back to the list without changing its structure.

  • Continue until all node values have been updated, ensuring every position in the linked list follows the sorted order.

  • Return the original head, as only the values inside the nodes have changed while the node connections remain unchanged.

Dry Run

sort ll

sort ll

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int data;
Node* next;
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Function to sort a linked list using value collection.
ListNode* sortList(ListNode* head) {
vector<int> values;
ListNode* current = head;
// Collect every node value inside an array.
while (current != nullptr) {
values.push_back(current->data);
current = current->next;
}
sort(values.begin(), values.end());
current = head;
int index = 0;
// Write sorted values back into existing nodes.
while (current != nullptr) {
current->data = values[index];
index++;
current = current->next;
}
return head;
}
};
// Function to create a linked list from an array.
ListNode* createList(vector<int>& arr) {
if (arr.empty()) return nullptr;
ListNode* head = new ListNode(arr[0]);
ListNode* current = head;
for (int index = 1; index < (int)arr.size(); index++) {
current->next = new ListNode(arr[index]);
current = current->next;
}
return head;
}
// Function to print linked list values.
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->data;
if (current->next != nullptr) cout << " ";
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr = {4, 2, 1, 3};
ListNode* head = createList(arr);
Solution sol;
head = sol.sortList(head);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), sorting N collected values dominates the two linked list traversals.

Space Complexity: O(N), array storage keeps all node values.

Optimal Approach

Merge sort is well suited for linked lists because it does not require random access. We first split the linked list into two halves using slow and fast pointers, recursively sort both halves, and then merge the two sorted lists by relinking the existing nodes.

Since each split divides the list into smaller parts and each merge processes every node exactly once, the algorithm efficiently sorts the linked list while using only pointer manipulations.

Algorithm

  • Return head when the linked list is empty or contains only one node, as a list with at most one element is already sorted.

  • Use slow and fast pointers to find the middle of the linked list, since moving slow one step and fast two steps makes slow reach the midpoint when fast reaches the end.

  • Split the linked list into two halves by detaching the second half from the first, as merge sort requires smaller independent lists before they can be sorted.

  • Recursively apply merge sort to both the left and right halves, since each half can be sorted using the same process until every part contains at most one node.

  • Merge the two sorted halves by repeatedly linking the node with the smaller current value, as both halves are already sorted and the smaller node must appear first in the merged list.

  • Continue the merge until all nodes from both halves have been connected, with any remaining nodes already being in sorted order.

  • Return the head of the merged sorted linked list, as the recursive sorting and merging have now produced the complete sorted sequence.

Dry Run

sort ll via merge sort

sort ll via merge sort

Solution

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
int data;
Node* next;
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Function to merge two sorted linked lists.
ListNode* mergeLists(ListNode* first, ListNode* second) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (first != nullptr && second != nullptr) {
if (first->data<= second->data) {
tail->next = first;
first = first->next;
} else {
tail->next = second;
second = second->next;
}
tail = tail->next;
}
tail->next = (first != nullptr) ? first : second;
return dummy.next;
}
// Function to find middle predecessor and split list.
ListNode* splitList(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* second = slow->next;
slow->next = nullptr;
return second;
}
// Function to sort a linked list using merge sort.
ListNode* sortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* second = splitList(head);
ListNode* left = sortList(head);
ListNode* right = sortList(second);
return mergeLists(left, right);
}
};
// Function to create a linked list from an array.
ListNode* createList(vector<int>& arr) {
if (arr.empty()) return nullptr;
ListNode* head = new ListNode(arr[0]);
ListNode* current = head;
for (int index = 1; index < (int)arr.size(); index++) {
current->next = new ListNode(arr[index]);
current = current->next;
}
return head;
}
// Function to print linked list values.
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->data;
if (current->next != nullptr) cout << " ";
current = current->next;
}
}
// Driver code.
int main() {
vector<int> arr = {4, 2, 1, 3};
ListNode* head = createList(arr);
Solution sol;
head = sol.sortList(head);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), every recursion level merges N nodes and the number of levels is log N.

Space Complexity: O(log N), recursion stack stores one frame per split level.

Interview follow-up Questions

Yes. Values can be collected into an array, sorted, and written back, but auxiliary space becomes O(N).

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.8k
Linked List

Merge Two Sorted Linked Lists

Given heads of two sorted linked lists, merge both lists into one sorted linked list and return the head of the merged list. Every node stores an integer value and a pointer to the next node. The f...

114.6k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the...

101.5k
Comments0