dev.to

Leetcode 148 : Sort List

Problem Statement https://leetcode.com/problems/sort-list/description/ Given the head of a linked list, return the list after sorting it in ascending order. Sample Test Cases Example 1: Input: head = [4,2,1,3] Output: [1,2,3,4] Example 2: Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5] Example 3: Input: head = [] Output: [] Constraints The number of nodes in the list is in the range [0, 5 * 104]. -10^5

Mar 29, 2025 - 19:43

Problem Statement

https://leetcode.com/problems/sort-list/description/

Given the head of a linked list, return the list after sorting it in ascending order.

Sample Test Cases

Example 1:

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

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

Input: head = []
Output: []

Constraints

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

Intuition

This is basically to sort the linked list using some sorting method. We can store this in a list, sort it using a library function, and reconstruct the linked list. This is correct, but we are not fully utilising the fact that the question is for a linked list.
We can just apply the merge sort, similar to the concept of merge sort in arrays, ie, divide and conquer.

Approach

Traverse the array and, using the slow, fast pointer method, find the middle of the linked list to differentiate between the left part and the right part.
Do this recursively and then merge the linked list.
Merging the linked list involves comparing the node values between the left part and the right.
Reuse the linked list instead of creating a new linked list to store the result.

Complexity

Time complexity:
O(NlogN)
Space complexity:
O(1), if we are not considering the recursion stack space.

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode previous = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            previous = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        previous.next = null;
        ListNode leftPart = sortList(head);
        ListNode rightPart = sortList(slow);
        ListNode merged = mergeLinkedList(leftPart, rightPart);
        return merged;
    }

    private ListNode mergeLinkedList(ListNode left, ListNode right) {
        if (left == null && right == null) {
            return null;
        }
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        ListNode leftPointer = left;
        ListNode rightPointer = right;
        ListNode result = new ListNode(0);
        ListNode current = result;
        while (leftPointer != null && rightPointer != null) {
            if (leftPointer.val <= rightPointer.val) {
                current.next = leftPointer;
                leftPointer = leftPointer.next;
                current = current.next;
            }
            else {
                current.next = rightPointer;
                rightPointer = rightPointer.next;
                current = current.next;
            }
        }
        if (leftPointer != null) {
            current.next = leftPointer;
                current = current.next;
        }
        else if (rightPointer != null) {
            current.next = rightPointer;
                current = current.next;
        }
        return result.next;
    }
}