Approach: Collect, sort, write back

def sortList(self, head):
    vals = []
    cur = head
    while cur:
        vals.append(cur.val)
        cur = cur.next
    vals.sort()
    cur = head
    i = 0
    while cur:
        cur.val = vals[i]
        i += 1
        cur = cur.next
    return head

Complexity: O(n log n) time, O(n) space.

Full Solution — all languages

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def sortList(self, head):
        vals = []
        cur = head
        while cur:
            vals.append(cur.val)
            cur = cur.next
        vals.sort()
        cur = head
        i = 0
        while cur:
            cur.val = vals[i]
            i += 1
            cur = cur.next
        return head

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
class Solution {
    public ListNode sortList(ListNode head) {
        java.util.List<Integer> vals = new java.util.ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            vals.add(cur.val);
            cur = cur.next;
        }
        java.util.Collections.sort(vals);
        cur = head;
        int i = 0;
        while (cur != null) {
            cur.val = vals.get(i++);
            cur = cur.next;
        }
        return head;
    }
}

#include <bits/stdc++.h> using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(nullptr) {
    }
};
class Solution {
    public: ListNode* sortList(ListNode* head) {
        vector<int> vals;
        ListNode* cur = head;
        while (cur) {
            vals.push_back(cur->val);
            cur = cur->next;
        }
        sort(vals.begin(), vals.end());
        cur = head;
        int i = 0;
        while (cur) {
            cur->val = vals[i++];
            cur = cur->next;
        }
        return head;
    }
};

/** Node shape: { val, next }. Build/return plain objects or use this ctor. */ function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}
/**
 * @param {ListNode} head
 * @return {ListNode}
 */ var sortList = function(head) {
    const vals = [];
    let cur = head;
    while (cur) {
        vals.push(cur.val);
        cur = cur.next;
    }
    vals.sort((a, b) => a - b);
    cur = head;
    let i = 0;
    while (cur) {
        cur.val = vals[i++];
        cur = cur.next;
    }
    return head;
};

Sort List

Example 1

Example 2

Constraints