148. Sort Linked List

Problem Statement

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

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 * 10<sup>4</sup>].

• -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>

Solution

Brute Force Approach

1. Gather all elements of the linked list into a list.

2. Sort the list.

3. Reintegrate the sorted sequence back into the linked list.

Time - O(n) + O(nlogn) + O(n) -> O(nlogn)

Space - O(n)

/**
 * 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) {
        List<Integer> arr = new ArrayList<>();

        ListNode temp = head;

        while(temp!=null){
            arr.add(temp.val);
            temp = temp.next;
        }

        Collections.sort(arr);

        temp = head;

        for(int element: arr){
            temp.val = element;
            temp = temp.next;
        }

        return head;
    }
}

Optimal Approach (Merge Sort)

We're using a method called merge sort (link) to organize our linked list. Unlike some other sorting techniques, we don't use specific numbers to decide how to sort. Instead, we split the list in half using two pointers, one for each half. We ensure that the end of the first half points to nothing, so we have two separate lists.

To figure out where to split the list, we use a trick called the tortoise and hare algorithm(link). We start one pointer at the beginning and another a bit ahead. The one that moves faster helps us find the middle of the list.

When combining two sorted linked lists, we don't need extra space because we can adjust the sequence by changing the next pointer address. We introduce an additional dummy node to indicate the merged sequence. We also use three temporary variables for managing the merged sequence and two more for iterating through the sorted linked list sequences. If one of the linked lists isn't fully traversed, we adjust the end pointer of the merged sequence to include the remaining part of that linked list.

Time - O(nlogn)

Space - O(1)

class Solution {
    private ListNode getMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;

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

    private ListNode merge(ListNode leftHead, ListNode rightHead){
        ListNode dummyNode = new ListNode(0);

        ListNode temp = dummyNode;
        ListNode temp1 = leftHead;
        ListNode temp2 = rightHead;

        while(temp1!=null && temp2!=null){
            if(temp1.val < temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
                temp = temp.next;
            }
            else{
                temp.next = temp2;
                temp2 = temp2.next;
                temp = temp.next;
            }
        }

        if(temp1!=null) temp.next = temp1;
        if(temp2!=null) temp.next = temp2;

        return dummyNode.next;
    }

    private ListNode mergeSort(ListNode head){
        if(head==null || head.next==null) 
            return head;
        ListNode middle = getMiddle(head);
        ListNode leftHead = head;
        ListNode rightHead = middle.next;
        middle.next = null;
        leftHead = mergeSort(leftHead);
        rightHead = mergeSort(rightHead);
        return merge(leftHead,rightHead);
    }

    public ListNode sortList(ListNode head) {
        return mergeSort(head);   
    }
}