LeetCode-in-All

148. Sort List

Medium

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

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].
• -105 <= Node.val <= 105

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Solution

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class Solution {
  ListNode? sortList(ListNode? head) {
    if (head == null || head.next == null) return head;

    // Get the middle of the list and split it into two halves
    ListNode? mid = getMidNode(head);

    // Recursively sort both halves
    ListNode? left = sortList(head);
    ListNode? right = sortList(mid);

    // Merge the sorted halves
    return mergeLists(left, right);
  }

  ListNode? mergeLists(ListNode? node1, ListNode? node2) {
    ListNode dummyHead = ListNode(); // Use a dummy node
    ListNode? tail = dummyHead;

    while (node1 != null && node2 != null) {
      if (node1.val <= node2.val) {
        tail?.next = node1;
        node1 = node1.next;
      } else {
        tail?.next = node2;
        node2 = node2.next;
      }
      tail = tail?.next;
    }

    // Append the remaining nodes
    tail?.next = (node1 != null) ? node1 : node2;
    return dummyHead.next;
  }

  ListNode? getMidNode(ListNode? head) {
    ListNode? fast = head;
    ListNode? slow = head;
    ListNode? prevSlow; // To disconnect the first half

    while (fast != null && fast.next != null) {
      prevSlow = slow;
      slow = slow?.next;
      fast = fast.next?.next;
    }

    // Disconnect the first half from the second half
    prevSlow?.next = null;
    return slow;
  }
}

This site is open source. Improve this page.