Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Definition for singly-linked list.
- * public class ListNode {
- * int val;
- * ListNode next;
- * ListNode(int x) { val = x; }
- * }
- */
- /*
- Refer: https://leetcode.com/problems/sort-list/discuss/46712/Bottom-to-up(not-recurring)-with-o(1)-space-complextity-and-o(nlgn)-time-complextity
- Time Complexity: O(n logn)
- Outer for loop runs for log n times. Inner while loop runs for 2 * n times.
- Space Complexity: O(1)
- This algorithm uses constant space.
- */
- class Solution {
- public ListNode sortList(ListNode head) {
- if (head == null || head.next == null) {
- return head;
- }
- ListNode cur = head;
- int length = 0;
- while (cur != null) {
- length++;
- cur = cur.next;
- }
- ListNode dummyNode = new ListNode(Integer.MIN_VALUE);
- dummyNode.next = head;
- for (int step = 1; step < length; step <<= 1) {
- cur = dummyNode.next;
- ListNode tail = dummyNode;
- while (cur != null) {
- ListNode left = cur;
- ListNode right = split(left, step);
- cur = split(right, step);
- tail = merge(tail, left, right);
- }
- }
- return dummyNode.next;
- }
- public ListNode split(ListNode head, int n) {
- for (int i = 1; i < n && head != null; i++) {
- head = head.next;
- }
- if (head == null) {
- return null;
- }
- ListNode next = head.next;
- head.next = null;
- return next;
- }
- public ListNode merge(ListNode head, ListNode l1, ListNode l2) {
- while (l1 != null && l2 != null) {
- if (l1.val <= l2.val) {
- head.next = l1;
- l1 = l1.next;
- } else {
- head.next = l2;
- l2 = l2.next;
- }
- head = head.next;
- }
- head.next = l1 == null ? l2 : l1;
- while (head.next != null) {
- head = head.next;
- }
- return head;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement