LeetCode [148] Sort List

 148. Sort List

Medium

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* sortList(ListNode* head){ int n = 0; ListNode *p = head; while(p){ ++n; p = p->next; } return divide(head, n); } ListNode* divide(ListNode *&head, int n){ if(n==0) return NULL; if(n==1){ ListNode* newHead = head; head = head->next; newHead->next = NULL; return newHead; } ListNode* head1 = divide(head, n/2); ListNode* head2 = divide(head, n-n/2); return merge(head1, head2); } ListNode* merge(ListNode *head1, ListNode *head2){ ListNode* sentinel = new ListNode(0); ListNode* p = sentinel; while(head1 && head2){ if(head1->val<head2->val){ p->next = head1; head1 = head1->next; }else{ p->next = head2; head2 = head2->next; } p = p->next; } if(head1) p->next = head1; if(head2) p->next = head2; return sentinel->next; } };