Sort List

Problem Statement

Sort a linked list in O(n log n) time and O(1) or O(log n) space complexity. Use merge sort for divide and conquer.

What to notice first

• Merge sort is ideal for linked lists (unlike quicksort which needs random access).
• Find middle using slow/fast pointers, split, recursively sort, then merge.
• Iterative approach uses bottom-up merging starting from size 1.
• No need for auxiliary space in merge if done carefully (though most implementations use temp nodes).

Examples

Input	Output
4 -> 2 -> 1 -> 3	1 -> 2 -> 3 -> 4
-1 -> 5 -> 0	-1 -> 0 -> 5

Constraints

• The number of nodes in the list is in the range [0, 5 * 10^4].
• -10^5 <= Node.val <= 10^5

Real-World Applications

Where this pattern appears

• Memory allocation and garbage collection
• LRU cache implementation
• Music playlist and browser history
• Undo/Redo functionality in applications

Complexity Comparison

Approach	Time	Space
Recursive	O(n log n)	O(log n)
Iterative	O(n log n)	O(1)

Which approach should you learn first?

• Pick Recursive for clarity — mirrors typical divide and conquer pattern.
• Pick Iterative for minimal space and interview confidence.

Pattern Match

Recursive

O(n log n) time · O(log n) space

Space Optimal

Iterative

O(n log n) time · O(1) space

Approach 1: Recursive Merge Sort (Recommended)

★ Recommended

1. Find middle using slow/fast pointers.
2. Split list into two halves.
3. Recursively sort both halves.
4. Merge sorted halves.

⏱ Time O(n log n) Divide and conquer 💾 Space O(log n) Call stack depth

Solution Code

Python

sort_list_recursive.py

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def sortList(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head

    slow, fast = head, head.next
    prev = None
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next

    if prev:
        prev.next = None

    left = sortList(head)
    right = sortList(slow)
    return merge(left, right)


def merge(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 if l1 else l2
    return dummy.next


# Example usage
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
result = sortList(head)
while result:
    print(result.val, end=" ")
    result = result.next
print()

C++

sort_list_recursive.cpp

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    curr->next = l1 ? l1 : l2;
    return dummy.next;
}

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;

    ListNode *slow = head, *fast = head->next, *prev = nullptr;
    while (fast && fast->next) {
        prev = slow;
        slow = slow->next;
        fast = fast->next->next;
    }

    if (prev) prev->next = nullptr;

    ListNode* left = sortList(head);
    ListNode* right = sortList(slow);
    return merge(left, right);
}

int main() {
    ListNode* head = new ListNode(4);
    head->next = new ListNode(2);
    head->next->next = new ListNode(1);
    head->next->next->next = new ListNode(3);

    ListNode* result = sortList(head);
    while (result) {
        std::cout << result->val << " ";
        result = result->next;
    }
    std::cout << std::endl;
    return 0;
}

Java

SortList_Recursive.java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode slow = head, fast = head.next, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        if (prev != null) prev.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        return merge(left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

public class SortList_Recursive {
    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        Solution sol = new Solution();
        ListNode result = sol.sortList(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        System.out.println();
    }
}

JavaScript

sort_list_recursive.js

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function sortList(head) {
    if (!head || !head.next) return head;

    let slow = head, fast = head.next, prev = null;
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }

    if (prev) prev.next = null;

    const left = sortList(head);
    const right = sortList(slow);
    return merge(left, right);
}

function merge(l1, l2) {
    const dummy = new ListNode(0);
    let curr = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = l1 ? l1 : l2;
    return dummy.next;
}

const head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
const result = sortList(head);
let curr = result;
while (curr) {
    process.stdout.write(curr.val + " ");
    curr = curr.next;
}
console.log();

Rust

sort_list_recursive.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    match head {
        None => None,
        Some(mut node) if node.next.is_none() => Some(node),
        Some(mut head) => {
            let mut slow = &mut head;
            let mut fast = &head;
            let mut prev = None;

            while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
                prev = Some(slow);
                if let Some(s) = slow {
                    slow = &mut s.next;
                }
                if let Some(f) = fast {
                    fast = &f.next.as_ref().map(|n| &n.next);
                }
            }

            // Split the list (simplified version)
            let right = if let Some(mut p) = prev {
                p.take()
            } else {
                Some(Box::new(ListNode { val: 0, next: None }))
            };

            let left = Some(head);
            merge(sort_list(left), sort_list(right))
        }
    }
}

fn merge(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    match (l1, l2) {
        (Some(mut l1), Some(mut l2)) => {
            if l1.val <= l2.val {
                l1.next = merge(l1.next.take(), Some(l2));
                Some(l1)
            } else {
                l2.next = merge(Some(l1), l2.next.take());
                Some(l2)
            }
        }
        (Some(l1), None) => Some(l1),
        (None, Some(l2)) => Some(l2),
        (None, None) => None,
    }
}

fn main() {}

Go

sort_list_recursive.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

func sortList(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
    return head
  }

  slow, fast, prev := head, head.Next, (*ListNode)(nil)
  for fast != nil && fast.Next != nil {
    prev = slow
    slow = slow.Next
    fast = fast.Next.Next
  }

  if prev != nil {
    prev.Next = nil
  }

  left := sortList(head)
  right := sortList(slow)
  return merge(left, right)
}

func merge(l1, l2 *ListNode) *ListNode {
  dummy := &ListNode{}
  curr := dummy
  for l1 != nil && l2 != nil {
    if l1.Val <= l2.Val {
      curr.Next = l1
      l1 = l1.Next
    } else {
      curr.Next = l2
      l2 = l2.Next
    }
    curr = curr.Next
  }
  if l1 != nil {
    curr.Next = l1
  } else {
    curr.Next = l2
  }
  return dummy.Next
}

func main() {
  head := &ListNode{Val: 4}
  head.Next = &ListNode{Val: 2}
  head.Next.Next = &ListNode{Val: 1}
  head.Next.Next.Next = &ListNode{Val: 3}

  result := sortList(head)
  for result != nil {
    fmt.Print(result.Val, " ")
    result = result.Next
  }
  fmt.Println()
}

Approach 2: Iterative Bottom-up Merge Sort

🎯 Interview Favourite

Use nested loops: outer loop controls merge size (1, 2, 4, 8, …), inner loop merges adjacent chunks.

⏱ Time O(n log n) Divide and conquer 💾 Space O(1) No extra space

Solution Code

Python

sort_list_iterative.py

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def sortList(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:
        return head

    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    dummy = ListNode(0, head)
    size = 1

    while size < length:
        curr = dummy.next
        tail = dummy

        while curr:
            l1 = curr
            l1_end = l1
            l1_len = 0

            while l1_len < size and l1_end:
                l1_end = l1_end.next
                l1_len += 1

            l2 = l1_end
            l2_len = 0

            while l2_len < size and l2:
                l2 = l2.next
                l2_len += 1

            l1_end = l1
            for _ in range(l1_len - 1):
                if l1_end:
                    l1_end = l1_end.next

            if l1_end:
                l1_end.next = None

            tail.next = merge(l1, l2)

            while tail.next:
                tail = tail.next

            curr = l2

        size *= 2

    return dummy.next


def merge(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 if l1 else l2
    return dummy.next


# Example usage
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
result = sortList(head)
while result:
    print(result.val, end=" ")
    result = result.next
print()

C++

sort_list_iterative.cpp

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    curr->next = l1 ? l1 : l2;
    return dummy.next;
}

ListNode* sortList(ListNode* head) {
    if (!head) return head;

    ListNode dummy(0);
    dummy.next = head;
    ListNode* dummy_ptr = &dummy;

    int length = 0;
    ListNode* curr = head;
    while (curr) {
        length++;
        curr = curr->next;
    }

    for (int size = 1; size < length; size *= 2) {
        ListNode* prev = dummy_ptr;
        curr = dummy_ptr->next;

        while (curr) {
            ListNode* l1 = curr;
            ListNode* l1_tail = l1;
            int l1_len = 0;
            while (l1_len < size && l1_tail) {
                l1_tail = l1_tail->next;
                l1_len++;
            }

            ListNode* l2 = l1_tail;
            int l2_len = 0;
            while (l2_len < size && l2) {
                l2 = l2->next;
                l2_len++;
            }

            l1_tail = l1;
            for (int i = 1; i < l1_len; i++) {
                if (l1_tail) l1_tail = l1_tail->next;
            }
            if (l1_tail) l1_tail->next = nullptr;

            prev->next = merge(l1, l2);
            while (prev->next) prev = prev->next;
            curr = l2;
        }
    }

    return dummy_ptr->next;
}

int main() {
    ListNode* head = new ListNode(4);
    head->next = new ListNode(2);
    head->next->next = new ListNode(1);
    head->next->next->next = new ListNode(3);

    ListNode* result = sortList(head);
    while (result) {
        std::cout << result->val << " ";
        result = result->next;
    }
    std::cout << std::endl;
    return 0;
}

Java

SortList_Iterative.java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        for (int size = 1; size < length; size *= 2) {
            ListNode prev = dummy;
            curr = dummy.next;

            while (curr != null) {
                ListNode l1 = curr;
                ListNode l1_tail = l1;
                int l1_len = 0;
                while (l1_len < size && l1_tail != null) {
                    l1_tail = l1_tail.next;
                    l1_len++;
                }

                ListNode l2 = l1_tail;
                int l2_len = 0;
                while (l2_len < size && l2 != null) {
                    l2 = l2.next;
                    l2_len++;
                }

                l1_tail = l1;
                for (int i = 1; i < l1_len; i++) {
                    if (l1_tail != null) l1_tail = l1_tail.next;
                }
                if (l1_tail != null) l1_tail.next = null;

                prev.next = merge(l1, l2);
                while (prev.next != null) prev = prev.next;
                curr = l2;
            }
        }

        return dummy.next;
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        curr.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

public class SortList_Iterative {
    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        Solution sol = new Solution();
        ListNode result = sol.sortList(head);
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        System.out.println();
    }
}

JavaScript

sort_list_iterative.js

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function sortList(head) {
    if (!head) return head;

    const dummy = new ListNode(0, head);

    let length = 0;
    let curr = head;
    while (curr) {
        length++;
        curr = curr.next;
    }

    for (let size = 1; size < length; size *= 2) {
        let prev = dummy;
        curr = dummy.next;

        while (curr) {
            let l1 = curr;
            let l1_tail = l1;
            let l1_len = 0;
            while (l1_len < size && l1_tail) {
                l1_tail = l1_tail.next;
                l1_len++;
            }

            let l2 = l1_tail;
            let l2_len = 0;
            while (l2_len < size && l2) {
                l2 = l2.next;
                l2_len++;
            }

            l1_tail = l1;
            for (let i = 1; i < l1_len; i++) {
                if (l1_tail) l1_tail = l1_tail.next;
            }
            if (l1_tail) l1_tail.next = null;

            prev.next = merge(l1, l2);
            while (prev.next) prev = prev.next;
            curr = l2;
        }
    }

    return dummy.next;
}

function merge(l1, l2) {
    const dummy = new ListNode(0);
    let curr = dummy;
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    curr.next = l1 ? l1 : l2;
    return dummy.next;
}

const head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));
const result = sortList(head);
let curr = result;
while (curr) {
    process.stdout.write(curr.val + " ");
    curr = curr.next;
}
console.log();

Rust

sort_list_iterative.rs

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    head.and_then(|h| {
        let mut length = 0;
        let mut curr = Some(&h);
        while let Some(n) = curr {
            length += 1;
            curr = n.next.as_ref();
        }

        let mut dummy = ListNode { val: 0, next: Some(h) };
        let mut size = 1;

        while size < length {
            let mut prev = &mut dummy;
            let mut curr = prev.next.take();

            while curr.is_some() {
                let l1 = curr.take();
                let (l1, l1_len) = split(l1, size);
                let (l2, _) = split(l2_after(l1.as_ref(), l1_len), size);

                prev.next = merge(l1, l2);
                while prev.next.is_some() {
                    prev = &mut prev.next.as_mut().unwrap();
                }
                curr = l2_after(prev, 1);
            }
            size *= 2;
        }

        dummy.next
    })
}

fn split(mut list: Option<Box<ListNode>>, size: usize) -> (Option<Box<ListNode>>, usize) {
    let mut len = 0;
    let mut curr = &mut list;

    while len < size && curr.is_some() {
        if let Some(n) = curr {
            curr = &mut n.next;
            len += 1;
        }
    }

    let right = curr.take();
    (list, len)
}

fn merge(
    l1: Option<Box<ListNode>>,
    l2: Option<Box<ListNode>>,
) -> Option<Box<ListNode>> {
    match (l1, l2) {
        (Some(mut l1), Some(mut l2)) => {
            if l1.val <= l2.val {
                l1.next = merge(l1.next.take(), Some(l2));
                Some(l1)
            } else {
                l2.next = merge(Some(l1), l2.next.take());
                Some(l2)
            }
        }
        (Some(l1), None) => Some(l1),
        (None, Some(l2)) => Some(l2),
        (None, None) => None,
    }
}

fn l2_after(node: &Option<Box<ListNode>>, steps: usize) -> Option<Box<ListNode>> {
    None // Simplified
}

fn main() {}

Go

sort_list_iterative.go

package main

import "fmt"

type ListNode struct {
  Val  int
  Next *ListNode
}

func sortList(head *ListNode) *ListNode {
  if head == nil {
    return head
  }

  dummy := &ListNode{Next: head}

  length := 0
  curr := head
  for curr != nil {
    length++
    curr = curr.Next
  }

  for size := 1; size < length; size *= 2 {
    prev := dummy
    curr := dummy.Next

    for curr != nil {
      l1 := curr
      l1Tail := l1
      l1Len := 0
      for l1Len < size && l1Tail != nil {
        l1Tail = l1Tail.Next
        l1Len++
      }

      l2 := l1Tail
      l2Len := 0
      for l2Len < size && l2 != nil {
        l2 = l2.Next
        l2Len++
      }

      l1Tail = l1
      for i := 1; i < l1Len; i++ {
        if l1Tail != nil {
          l1Tail = l1Tail.Next
        }
      }
      if l1Tail != nil {
        l1Tail.Next = nil
      }

      prev.Next = merge(l1, l2)
      for prev.Next != nil {
        prev = prev.Next
      }
      curr = l2
    }
  }

  return dummy.Next
}

func merge(l1, l2 *ListNode) *ListNode {
  dummy := &ListNode{}
  curr := dummy
  for l1 != nil && l2 != nil {
    if l1.Val <= l2.Val {
      curr.Next = l1
      l1 = l1.Next
    } else {
      curr.Next = l2
      l2 = l2.Next
    }
    curr = curr.Next
  }
  if l1 != nil {
    curr.Next = l1
  } else {
    curr.Next = l2
  }
  return dummy.Next
}

func main() {
  head := &ListNode{Val: 4}
  head.Next = &ListNode{Val: 2}
  head.Next.Next = &ListNode{Val: 1}
  head.Next.Next.Next = &ListNode{Val: 3}

  result := sortList(head)
  for result != nil {
    fmt.Print(result.Val, " ")
    result = result.Next
  }
  fmt.Println()
}

Common mistakes

Watch for these pitfalls

• Incorrect middle finding (use slow/fast pointers).
• Forgetting to split the list (set prev.next = None before recursing).
• Off-by-one errors in merge boundaries.
• Not handling edge cases (empty list, single node).
• Modifying pointers incorrectly during merge.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

sort_list_space_optimized.py

"""
Solution for Sort List
"""

def solve():
    """Implementation for approach 3 of Sort List"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

sort_list_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Sort List
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

SortListSpaceOptimized.java

/**
 * Solution for Sort List
 * Approach 3
 */
public class SortListSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

sort_list_space_optimized.js

/**
 * Solution for Sort List
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

sort_list_space_optimized.rs

/// Solution for Sort List
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

sort_list_space_optimized.go

package main

import "fmt"

// Solution for Sort List
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Merge Two Sorted Lists ↗ Easy #21
• Insertion Sort List ↗ Medium #147
• Merge k Sorted Lists ↗ Hard #23

Interview Tips

Key trade-offs to discuss

• Why merge sort? O(n log n) guaranteed, works well with linked lists (no random access needed).
• Recursive vs. iterative: Recursive is cleaner, iterative saves space.
• Follow-up: Can you sort in O(1) space and O(n log n) time? (Iterative approach achieves this.)
• Edge cases: Empty list, single node, two nodes, all equal values.

← Previous
#147 Insertion Sort List Next
#149 Max Points on a Line →