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; } }