Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/148.html

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

Algorithm

The title limits the time to be O(nlgn). Only

  • quick sort,
  • merge sort, and
  • heap sort

meet the requirements. According to the characteristics of singly linked lists, merge sort is most suitable.

To do merge sort, the middle node of the list should be found.

  • Use two pointers to find the middle node. Each time the fast pointer moves two steps and the slow pointer moves one step.
  • When the fast pointer moves to the end, the slow pointer points the middle node.
  • After finding the middle node, do merge sort for two parts of the node respectively, and merge the two parts after both parts are sorted.

Two merge two parts of a list, always find the node with the smallest number each time and append the node to the sorted list.

Code

  • 
    public class Sort_List {
    
        public class Solution {
            /**
             * Definition for singly-linked list.
             * class ListNode {
             * int val;
             * ListNode next;
             * ListNode(int x) {
             * val = x;
             * next = null;
             * }
             * }
             */
    
            public ListNode sortList(ListNode head) {
                if (head == null || head.next == null) return head;
    
                ListNode dummy = new ListNode(0);
                dummy.next = head;
    
                ListNode prev = dummy;
                ListNode slow = head;
                ListNode fast = head;
    
                // 每次都要找中点,复杂度略高啊
                while (fast != null && fast.next != null) {
                    prev = slow;
                    slow = slow.next;
                    fast = fast.next.next;
                }
    
                ListNode left = head; // eg. [1,2]
                ListNode right = slow;
                prev.next = null; // cut
    
                ListNode sortedLeft = sortList(left);
                ListNode sortedRight = sortList(right);
    
                return mergeSorted(sortedLeft, sortedRight);
            }
    
            public ListNode mergeSorted(ListNode left, ListNode right) {
                ListNode dummy = new ListNode(0);
    
                ListNode current = dummy;
    
                while (left != null || right != null) {
                    int lval = left == null ? Integer.MAX_VALUE : left.val;
                    int rval = right == null ? Integer.MAX_VALUE : right.val;
    
                    if (lval < rval) {
                        current.next = new ListNode(lval);
                        left = left.next; // I missed this...
                    } else {
                        current.next = new ListNode(rval);
                        right = right.next;
                    }
    
                    current = current.next;
                }
    
                return dummy.next;
            }
        }
    
    
        // constant extra space using Bottom Up Approach
        class Solution_bottom_up_merge_sort {
            ListNode tail = new ListNode(0);
            ListNode nextSubList = new ListNode(0);
    
            public ListNode sortList(ListNode head) {
                if (head == null || head.next == null)
                    return head;
                int n = getCount(head);
                ListNode start = head;
                ListNode dummyHead = new ListNode(0);
                for (int size = 1; size < n; size = size * 2) {
                    tail = dummyHead;
                    while (start != null) {
                        if (start.next == null) {
                            tail.next = start;
                            break;
                        }
                        ListNode mid = split(start, size);
                        merge(start, mid);
                        start = nextSubList;
                    }
                    start = dummyHead.next;
                }
                return dummyHead.next;
            }
    
            ListNode split(ListNode start, int size) {
                ListNode midPrev = start;
                ListNode end = start.next;
                //use fast and slow approach to find middle and end of second linked list
                for (int index = 1; index < size && (midPrev.next != null || end.next != null); index++) {
                    if (end.next != null) {
                        end = (end.next.next != null) ? end.next.next : end.next;
                    }
                    if (midPrev.next != null) {
                        midPrev = midPrev.next;
                    }
                }
                ListNode mid = midPrev.next;
                midPrev.next = null;
                nextSubList = end.next;
                end.next = null;
                // return the start of second linked list
                return mid;
            }
    
            void merge(ListNode list1, ListNode list2) {
                ListNode dummyHead = new ListNode(0);
                ListNode newTail = dummyHead;
                while (list1 != null && list2 != null) {
                    if (list1.val < list2.val) {
                        newTail.next = list1;
                        list1 = list1.next;
                        newTail = newTail.next;
                    } else {
                        newTail.next = list2;
                        list2 = list2.next;
                        newTail = newTail.next;
                    }
                }
                newTail.next = (list1 != null) ? list1 : list2;
                // traverse till the end of merged list to get the newTail
                while (newTail.next != null) {
                    newTail = newTail.next;
                }
                // link the old tail with the head of merged list
                tail.next = dummyHead.next;
                // update the old tail to the new tail of merged list
                tail = newTail;
            }
    
            int getCount(ListNode head) {
                int cnt = 0;
                ListNode ptr = head;
                while (ptr != null) {
                    ptr = ptr.next;
                    cnt++;
                }
                return cnt;
            }
        }
    
    }
    
    ############
    
    /**
     * 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, fast = head.next;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode t = slow.next;
            slow.next = null;
            ListNode l1 = sortList(head);
            ListNode l2 = sortList(t);
            ListNode dummy = new ListNode();
            ListNode cur = dummy;
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    cur.next = l1;
                    l1 = l1.next;
                } else {
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            cur.next = l1 == null ? l2 : l1;
            return dummy.next;
        }
    }
    
  • // OJ: https://leetcode.com/problems/sort-list/
    // Time: O(NlogN)
    // Space: O(logN)
    class Solution {
        ListNode* splitList(ListNode *head) {
            ListNode dummy, *p = &dummy, *q = &dummy;
            dummy.next = head;
            while (q && q->next) {
                q = q->next->next;
                p = p->next;
            }
            auto next = p->next;
            p->next = NULL;
            return next;
        }
        ListNode *mergeList(ListNode *a, ListNode *b) {
            ListNode head, *tail = &head;
            while (a && b) {
                ListNode *node;
                if (a->val <= b->val) {
                    node = a;
                    a = a->next;
                } else {
                    node = b;
                    b = b->next;
                }
                tail->next = node;
                tail = node;
            }
            if (a) tail->next = a;
            if (b) tail->next = b;
            return head.next;
        }
    public:
        ListNode* sortList(ListNode* head) {
            if (!head || !head->next) return head;
            auto b = splitList(head);
            return mergeList(sortList(head), sortList(b));
        }
    };
    
  • # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def sortList(self, head: ListNode) -> ListNode:
            if head is None or head.next is None:
                return head
            slow, fast = head, head.next
            while fast and fast.next:
                slow, fast = slow.next, fast.next.next
            t = slow.next
            slow.next = None
            l1, l2 = self.sortList(head), self.sortList(t)
            dummy = ListNode()
            cur = dummy
            while l1 and l2:
                if l1.val <= l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            cur.next = l1 or l2
            return dummy.next
    
    ############
    
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
      def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head:
          fast = slow = head
          pre = None
    
          while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
    
          if not pre:
            return head
          pre.next = None
    
          left = self.sortList(head)
          right = self.sortList(slow)
    
          p = dummy = ListNode(-1)
          while left and right:
            if left.val < right.val:
              p.next = left
              left = left.next
            else:
              p.next = right
              right = right.next
            p = p.next
    
          if left:
            p.next = left
          if right:
            p.next = right
          return dummy.next
    
    
  • /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func sortList(head *ListNode) *ListNode {
    	if head == nil || head.Next == nil {
    		return head
    	}
    	slow, fast := head, head.Next
    	for fast != nil && fast.Next != nil {
    		slow, fast = slow.Next, fast.Next.Next
    	}
    	t := slow.Next
    	slow.Next = nil
    	l1, l2 := sortList(head), sortList(t)
    	dummy := &ListNode{}
    	cur := dummy
    	for l1 != nil && l2 != nil {
    		if l1.Val <= l2.Val {
    			cur.Next = l1
    			l1 = l1.Next
    		} else {
    			cur.Next = l2
    			l2 = l2.Next
    		}
    		cur = cur.Next
    	}
    	if l1 != nil {
    		cur.Next = l1
    	} else {
    		cur.Next = l2
    	}
    	return dummy.Next
    }
    
  • /**
     * Definition for singly-linked list.
     * class ListNode {
     *     val: number
     *     next: ListNode | null
     *     constructor(val?: number, next?: ListNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.next = (next===undefined ? null : next)
     *     }
     * }
     */
    
    function sortList(head: ListNode | null): ListNode | null {
        if (head == null || head.next == null) return head;
        // 快慢指针定位中点
        let slow: ListNode = head,
            fast: ListNode = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 归并排序
        let mid: ListNode = slow.next;
        slow.next = null;
        let l1: ListNode = sortList(head);
        let l2: ListNode = sortList(mid);
        let dummy: ListNode = new ListNode();
        let cur: ListNode = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
    
    
  • /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    var sortList = function (head) {
        if (!head || !head.next) {
            return head;
        }
        let slow = head;
        let fast = head.next;
        while (fast && fast.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        let t = slow.next;
        slow.next = null;
        let l1 = sortList(head);
        let l2 = sortList(t);
        const dummy = new ListNode();
        let cur = dummy;
        while (l1 && l2) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 || l2;
        return dummy.next;
    };
    
    
  • /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     public int val;
     *     public ListNode next;
     *     public ListNode(int val=0, ListNode next=null) {
     *         this.val = val;
     *         this.next = next;
     *     }
     * }
     */
    public class Solution {
        public ListNode SortList(ListNode head) {
            if (head == null || head.next == null)
            {
                return head;
            }
            ListNode slow = head, fast = head.next;
            while (fast != null && fast.next != null)
            {
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode t = slow.next;
            slow.next = null;
            ListNode l1 = SortList(head);
            ListNode l2 = SortList(t);
            ListNode dummy = new ListNode();
            ListNode cur = dummy;
            while (l1 != null && l2 != null)
            {
                if (l1.val <= l2.val)
                {
                    cur.next = l1;
                    l1 = l1.next;
                }
                else
                {
                    cur.next = l2;
                    l2 = l2.next;
                }
                cur = cur.next;
            }
            cur.next = l1 == null ? l2 : l1;
            return dummy.next;
        }
    }
    
  • // Definition for singly-linked list.
    // #[derive(PartialEq, Eq, Clone, Debug)]
    // pub struct ListNode {
    //   pub val: i32,
    //   pub next: Option<Box<ListNode>>
    // }
    //
    // impl ListNode {
    //   #[inline]
    //   fn new(val: i32) -> Self {
    //     ListNode {
    //       next: None,
    //       val
    //     }
    //   }
    // }
    impl Solution {
        pub fn sort_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
            fn merge(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
                match (l1, l2) {
                    (None, Some(node)) | (Some(node), None) => Some(node),
                    (Some(mut node1), Some(mut node2)) => {
                        if node1.val < node2.val {
                            node1.next = merge(node1.next.take(), Some(node2));
                            Some(node1)
                        } else {
                            node2.next = merge(Some(node1), node2.next.take());
                            Some(node2)
                        }
                    }
                    _ => None,
                }
            }
    
            fn sort(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
                if head.is_none() || head.as_ref().unwrap().next.is_none() {
                    return head;
                }
                let mut head = head;
                let mut length = 0;
                let mut cur = &head;
                while cur.is_some() {
                    length += 1;
                    cur = &cur.as_ref().unwrap().next;
                }
                let mut cur = &mut head;
                for _ in 0..(length / 2 - 1) {
                    cur = &mut cur.as_mut().unwrap().next;
                }
                let right = cur.as_mut().unwrap().next.take();
    
                merge(sort(head), sort(right))
            }
            sort(head)
        }
    }
    
    

All Problems

All Solutions