148. Sort List LeetCode Solution

In this guide, you will get 148. Sort List LeetCode Solution with the best time and space complexity. The solution to Sort List problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sort List solution in C++
Sort List solution in Java
Sort List solution in Python
Additional Resources

Problem Statement of Sort List

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)?

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(1)

148. Sort List LeetCode Solution in C++

class Solution {
 public:
  ListNode* sortList(ListNode* head) {
    const int length = getLength(head);
    ListNode dummy(0, head);

    for (int k = 1; k < length; k *= 2) {
      ListNode* curr = dummy.next;
      ListNode* tail = &dummy;
      while (curr != nullptr) {
        ListNode* l = curr;
        ListNode* r = split(l, k);
        curr = split(r, k);
        auto [mergedHead, mergedTail] = merge(l, r);
        tail->next = mergedHead;
        tail = mergedTail;
      }
    }

    return dummy.next;
  }

 private:
  int getLength(ListNode* head) {
    int length = 0;
    for (ListNode* curr = head; curr; curr = curr->next)
      ++length;
    return length;
  }

  ListNode* split(ListNode* head, int k) {
    while (--k && head)
      head = head->next;
    ListNode* rest = head ? head->next : nullptr;
    if (head != nullptr)
      head->next = nullptr;
    return rest;
  }

  pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (l1 && l2) {
      if (l1->val > l2->val)
        swap(l1, l2);
      tail->next = l1;
      l1 = l1->next;
      tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    while (tail->next != nullptr)
      tail = tail->next;

    return {dummy.next, tail};
  }
};
/* code provided by PROGIEZ */

148. Sort List LeetCode Solution in Java

class Solution {
  public ListNode sortList(ListNode head) {
    final int length = getLength(head);
    ListNode dummy = new ListNode(0, head);

    for (int k = 1; k < length; k *= 2) {
      ListNode curr = dummy.next;
      ListNode tail = dummy;
      while (curr != null) {
        ListNode l = curr;
        ListNode r = split(l, k);
        curr = split(r, k);
        ListNode[] merged = merge(l, r);
        tail.next = merged[0];
        tail = merged[1];
      }
    }

    return dummy.next;
  }

  private int getLength(ListNode head) {
    int length = 0;
    for (ListNode curr = head; curr != null; curr = curr.next)
      ++length;
    return length;
  }

  private ListNode split(ListNode head, int k) {
    while (--k > 0 && head != null)
      head = head.next;
    ListNode rest = head == null ? null : head.next;
    if (head != null)
      head.next = null;
    return rest;
  }

  private ListNode[] merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (l1 != null && l2 != null) {
      if (l1.val > l2.val) {
        ListNode temp = l1;
        l1 = l2;
        l2 = temp;
      }
      tail.next = l1;
      l1 = l1.next;
      tail = tail.next;
    }
    tail.next = l1 == null ? l2 : l1;
    while (tail.next != null)
      tail = tail.next;

    return new ListNode[] {dummy.next, tail};
  }
}
// code provided by PROGIEZ

148. Sort List LeetCode Solution in Python

class Solution:
  def sortList(self, head: ListNode) -> ListNode:
    def split(head: ListNode, k: int) -> ListNode:
      while k > 1 and head:
        head = head.next
        k -= 1
      rest = head.next if head else None
      if head:
        head.next = None
      return rest

    def merge(l1: ListNode, l2: ListNode) -> tuple:
      dummy = ListNode(0)
      tail = dummy

      while l1 and l2:
        if l1.val > l2.val:
          l1, l2 = l2, l1
        tail.next = l1
        l1 = l1.next
        tail = tail.next
      tail.next = l1 if l1 else l2
      while tail.next:
        tail = tail.next

      return dummy.next, tail

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

    dummy = ListNode(0, head)

    k = 1
    while k < length:
      curr = dummy.next
      tail = dummy
      while curr:
        l = curr
        r = split(l, k)
        curr = split(r, k)
        mergedHead, mergedTail = merge(l, r)
        tail.next = mergedHead
        tail = mergedTail
      k *= 2

    return dummy.next
 # code by PROGIEZ