Merge Sort for Linked Lists Hard 0 attempts
GeeksforGeeks ↗

Merge Sort for Linked Lists

Hard Linked List GeeksforGeeks

Sort a linked list using merge sort algorithm. Given a linked list represented as an array, return the sorted array. Merge sort divides the list into halves, recursively sorts each half, then merges the sorted halves back together.

Example 1:

Input: arr = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: arr = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Sample Input
—
Sample Output
—
Constraints
  • 0 <= number of nodes <= 5 * 10^4
  • -10^5 <= Node.val <= 10^5
Test Cases
Case 1
Args: [[4,2,1,3]] Expected: [1,2,3,4]
Case 2
Args: [[-1,5,3,4,0]] Expected: [-1,0,3,4,5]
Topics
Linked List

Approach: Recursive Merge Sort

Split the array in half, recursively sort both halves, then merge them using two pointers. This mirrors the linked list approach where you split with slow/fast pointers and merge sorted sublists.

function mergeSortForLinkedLists(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSortForLinkedLists(arr.slice(0, mid));
  const right = mergeSortForLinkedLists(arr.slice(mid));
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length)
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  return result.concat(left.slice(i), right.slice(j));
}

Time Complexity: O(n log n)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript