Sort List

Medium Linked List

Adobe

Amazon

Apple

Bloomberg

ByteDance

Capital One

Facebook

Google

IBM

Microsoft

Oracle

VMware

Yahoo

eBay

2020-09-30

148. Sort List

Question:

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

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

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

Solution:

Break the listnode into two parts and then merge the list back. Time Complexity: O(nlogn)

/**
 * 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 slow = head;
        ListNode fast = head;
        ListNode prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        return mergeList(sortList(head), sortList(slow));
    }
    
    private ListNode mergeList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode head = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                dummy.next = l1;
                l1 = l1.next;
                
            } else {
                dummy.next = l2;
                l2 = l2.next;
            }
            dummy = dummy.next;
            dummy.next = null;
        }
        if (l1 != null) {
            dummy.next = l1;
        } else {
            dummy.next = l2;
        }
        return head.next;
    }
}

Another way is using PriorityQueue to add all node in to the queue and the deque from it.

/**
 * 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) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
           @Override
            public int compare(ListNode l1, ListNode l2) {
                return l1.val - l2.val;
            }
        });
        while(head != null) {
            pq.offer(head);
            head = head.next;
        }
        ListNode dummy = new ListNode();
        ListNode result = dummy;
        
        while(!pq.isEmpty()) {
            dummy.next = pq.poll();
            dummy.next.next = null;
            dummy = dummy.next;
        }
        
        return result.next;
    }
}