148. Sort List – Leetcode Solutions

July 27, 2024

Table of Contents

Description

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

Examples:

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: []

Solution in Python

To sort a linked list in ascending order with constraints of O(n log ⁡n) time complexity and O(1) memory (constant space), we can use merge sort. Merge sort is a suitable choice because it naturally fits the linked list structure and provides the desired time complexity.

Detailed implementation of the solution:

Define the ListNode class: This class represents a node in a singly-linked list.
Implement the findMiddle function: This function will find the middle of the linked list using the fast and slow pointer technique.
Implement the merge function: This function will merge two sorted linked lists into one sorted linked list.
Implement the sortList function: This function will perform the merge sort algorithm recursively.

Python

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def findMiddle(self, head: ListNode) -> ListNode:
        # This function uses the fast and slow pointer technique to find the middle of the linked list
        slow = head
        fast = head
        prev = None
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        if prev:
            prev.next = None  # Split the list into two halves
        return slow

    def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
        # This function merges two sorted linked lists
        dummy = ListNode(0)
        current = dummy
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        if l1:
            current.next = l1
        if l2:
            current.next = l2
        return dummy.next

    def sortList(self, head: ListNode) -> ListNode:
        # Base case: if the list is empty or has only one element, it is already sorted
        if not head or not head.next:
            return head
        
        # Step 1: Find the middle of the linked list
        mid = self.findMiddle(head)
        
        # Step 2: Recursively sort the left and right halves
        left = self.sortList(head)
        right = self.sortList(mid)
        
        # Step 3: Merge the sorted halves
        return self.merge(left, right)

Explanation:

ListNode class: Represents each node in the linked list.
findMiddle method:
- Uses two pointers, slow and fast, to find the middle node of the list. The fast pointer moves twice as fast as the slow pointer.
- Splits the list into two halves by setting the next pointer of the node before the middle to None.
merge method:
- Merges two sorted linked lists into one sorted linked list.
- Uses a dummy node to simplify the merge process.
sortList method:
- Base case: If the list is empty or has only one node, it’s already sorted.
- Recursively splits the list into two halves until base cases are reached.
- Merges the sorted halves together.

Solution in Javascript

JavaScript

/**
 * Function to find the middle of the linked list
 * @param {ListNode} head
 * @return {ListNode}
 */
function findMiddle(head) {
    let slow = head;
    let fast = head;
    let prev = null;
    
    while (fast !== null && fast.next !== null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // Split the list into two halves
    if (prev !== null) {
        prev.next = null;
    }
    
    return slow;
}

/**
 * Function to merge two sorted linked lists
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
function merge(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
    
    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    
    if (l1 !== null) {
        current.next = l1;
    }
    
    if (l2 !== null) {
        current.next = l2;
    }
    
    return dummy.next;
}

/**
 * Function to sort the linked list using merge sort
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    // Base case: if the list is empty or has only one element, it is already sorted
    if (head === null || head.next === null) {
        return head;
    }
    
    // Step 1: Find the middle of the linked list
    let mid = findMiddle(head);
    
    // Step 2: Recursively sort the left and right halves
    let left = sortList(head);
    let right = sortList(mid);
    
    // Step 3: Merge the sorted halves
    return merge(left, right);
};

Solution in Java

Java

class Solution {
    // Method to find the middle of the linked list
    private ListNode findMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;
        
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        if (prev != null) {
            prev.next = null; // Split the list into two halves
        }
        
        return slow;
    }

    // Method to merge two sorted linked lists
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        if (l1 != null) {
            current.next = l1;
        }
        
        if (l2 != null) {
            current.next = l2;
        }
        
        return dummy.next;
    }

    // Method to sort the linked list using merge sort
    public ListNode sortList(ListNode head) {
        // Base case: if the list is empty or has only one element, it is already sorted
        if (head == null || head.next == null) {
            return head;
        }
        
        // Step 1: Find the middle of the linked list
        ListNode mid = findMiddle(head);
        
        // Step 2: Recursively sort the left and right halves
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        
        // Step 3: Merge the sorted halves
        return merge(left, right);
    }
}

Solution in C#

C#

public class Solution {
    // Method to find the middle of the linked list
    private ListNode FindMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;
        
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        
        if (prev != null) {
            prev.next = null; // Split the list into two halves
        }
        
        return slow;
    }

    // Method to merge two sorted linked lists
    private ListNode Merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        if (l1 != null) {
            current.next = l1;
        }
        
        if (l2 != null) {
            current.next = l2;
        }
        
        return dummy.next;
    }

    // Method to sort the linked list using merge sort
    public ListNode SortList(ListNode head) {
        // Base case: if the list is empty or has only one element, it is already sorted
        if (head == null || head.next == null) {
            return head;
        }
        
        // Step 1: Find the middle of the linked list
        ListNode mid = FindMiddle(head);
        
        // Step 2: Recursively sort the left and right halves
        ListNode left = SortList(head);
        ListNode right = SortList(mid);
        
        // Step 3: Merge the sorted halves
        return Merge(left, right);
    }
}

148. Sort List – Leetcode Solutions

Description

Solution in Python

Explanation:

Solution in Javascript

Solution in Java

Solution in C#

Popular

162. Find Peak Element – Leetcode Solutions

322. Coin Change – Leetcode Solutions

188. Best Time to Buy and Sell Stock IV – Leetcode Solutions

The bisect module in Python

344. Reverse String – Leetcode Solutions

154. Find Minimum in Rotated Sorted Array II – Leetcode Solutions

352. Data Stream as Disjoint Intervals – Leetcode Solutions

148. Sort List – Leetcode Solutions

Description

Solution in Python

Explanation:

Solution in Javascript

Solution in Java

Solution in C#

Related Post

Popular