package com.algorithms;

/**

* 经典问题: 排序链表

* 在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序。

* <p>

* 示例 1:

* <p>

* 输入: 4->2->1->3

* 输出: 1->2->3->4

* 示例 2:

* <p>

* 输入: -1->5->3->4->0

* 输出: -1->0->3->4->5

* <p>

* 来源：力扣（LeetCode）

* 链接：https://leetcode-cn.com/problems/sort-list

* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*

* <p>

* Created by xifeng.yang on 2020/1/31

*/

public class SortedList {

public static void main(String[] args) {

ListNode head = new ListNode(5);

ListNode node2 = new ListNode(3);

ListNode node3 = new ListNode(2);

ListNode node4 = new ListNode(4);

head.next = node2;

node2.next = node3;

node3.next = node4;

SortedList o = new SortedList();

ListNode newHead = o.sortList(head);

}

private static class ListNode {

int val;

ListNode next;

ListNode(int item) {

val = item;

}

}

/**

* 解法一: 交换结点元素

*

* @param head

* @return

*/

public ListNode sortList(ListNode head) {

if (head == null || head.next == null) {

return head;

}

ListNode cur = head;

while (cur != null) {

ListNode next = cur.next;

while (next != null) {

if (next.val < cur.val) {

int temp = next.val;

next.val = cur.val;

cur.val = temp;

}

next = next.next;

}

cur = cur.next;

}

return head;

}

/**

* 执行用时: 321 ms, 在所有 Java 提交中击败了13.48%的用户;

* 内存消耗: 40.6 MB, 在所有 Java 提交中击败了25.11%的用户.

*

* @param head

* @return

*/

public ListNode sortList2(ListNode head) {

if (head == null || head.next == null) {

return head;

}

ListNode dummyHead = new ListNode(0);

dummyHead.next = head;

ListNode cur = head.next;

ListNode pre = head;

while (cur != null) {

if (cur.val < pre.val) {

pre.next = cur.next;

ListNode pre2 = dummyHead;

ListNode cur2 = dummyHead.next;

while (cur.val > cur2.val) {

pre2 = cur2;

cur2 = cur2.next;

}

//把cur节点插入到pre1和cur1之间

pre2.next = cur;

cur.next = cur2;

cur = pre.next;

} else {

//向后移动

pre = cur;

cur = cur.next;

}

}

return dummyHead.next;

}

/**

* 执行用时: 618 ms, 在所有 Java 提交中击败了11.02%的用户,

* 内存消耗: 40.1 MB, 在所有 Java 提交中击败了60.43%的用户.

*/

public ListNode sortList3(ListNode head) {

if (head == null || head.next == null) {

return head;

}

ListNode dummyHead = new ListNode(0);

dummyHead.next = head;

return quickSort(dummyHead, null);

}

/**

* 解法: 自顶向下的归并排序

* 执行用时: 4 ms, 在所有 Java 提交中击败了81.28%的用户,

* 内存消耗: 40.3 MB, 在所有 Java 提交中击败了45.29%的用户.

*

* @param head

* @return

*/

public ListNode sortList4(ListNode head) {

if (head == null || head.next == null) {

return head;

}

ListNode fast = head.next;

ListNode slow = head;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

}

ListNode mid = slow.next;

slow.next = null;

ListNode left = sortList(head);

ListNode right = sortList(mid);

return merge(left, right);

}

private ListNode merge(ListNode left, ListNode right) {

ListNode newDummy = new ListNode(0);

ListNode tail = newDummy;

while (left != null && right != null) {

if (left.val <= right.val) {

tail.next = left;

left = left.next;

} else {

tail.next = right;

right = right.next;

}

tail = tail.next;

}

tail.next = left != null ? left : right;

return newDummy.next;

}

public ListNode sortList5(ListNode head) {

if (head == null || head.next == null) {

return head;

}

int len = 0;

while (head != null) {

len++;

head = head.next;

}

ListNode dummyHead = new ListNode(0);

dummyHead.next = head;

for (int step = 1; step < len; step *= 2) {

//从lo起所剩元素>step时才需要进行merge.

for (int lo = 0; lo < len - step; lo += step * 2) {

}

}

return dummyHead.next;

}

/**

* 解法: 自底向上的归并排序.

* 执行用时: 10 ms, 在所有 Java 提交中击败了27.36%的用户;

* 内存消耗: 40.6 MB, 在所有 Java 提交中击败了25.93%的用户.

*

* @param head

* @return

*/

public ListNode sortListOld(ListNode head) {

if (head == null || head.next == null) {

return head;

}

ListNode cur, h1, h2, pre;

cur = head;

int length = 0;

while (cur != null) {

cur = cur.next;

length++;

}

ListNode dummy = new ListNode(0);

dummy.next = head;

for (int step = 1; step < length; step *= 2) {

pre = dummy;

cur = dummy.next;

while (cur != null) {

int i = step;

h1 = cur;

while (i > 0 && cur != null) {

cur = cur.next;

i--;

}

if (i > 0 || cur == null) {

//从cur到尾部<=step个结点.

break;

}

i = step;

h2 = cur;

while (i > 0 && cur != null) {

cur = cur.next;

i--;

}

int c1 = step;

//i>0表示从h2起到尾部<step个结点.

int c2 = step - i;

while (c1 > 0 && c2 > 0) {

if (h1.val < h2.val) {

pre.next = h1;

h1 = h1.next;

c1--;

} else {

pre.next = h2;

h2 = h2.next;

c2--;

}

pre = pre.next;

}

pre.next = c1 == 0 ? h2 : h1;

//将pre推进到最后一个结点.

while (c1 > 0 || c2 > 0) {

pre = pre.next;

c1--;

c2--;

}

pre.next = cur;

}

}

return dummy.next;

}

private ListNode quickSort(ListNode head, ListNode end) {

if (head == end || head.next == end || head.next.next == end) {

return head;

}

ListNode newDummyHead = new ListNode(0);

ListNode partition = head.next;

ListNode pre = partition;

ListNode cur = partition.next;

ListNode tail = newDummyHead;

while (cur != end) {

if (cur.val < partition.val) {

pre.next = cur.next;

tail.next = cur;

tail = tail.next;

cur = pre.next;

} else {

pre = cur;

cur = cur.next;

}

}

tail.next = partition;

head.next = newDummyHead.next;

quickSort(head, partition);

quickSort(partition, end);

return head.next;

}

}