参考：
https://leetcode-cn.com/problems/sort-list
https://blog.csdn.net/Jacketinsysu/article/details/52472364?utm_source=blogkpcl7
https://zhuanlan.zhihu.com/p/85122573 【插入排序todo】
https://zhuanlan.zhihu.com/p/90106653
148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
/**
* 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) {
}
}
题解：https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
解答一：归并排序（递归法）
public class SortList148 { public static void main(String[] args) { ListNode listNode1 = new ListNode(4); ListNode listNode2 = new ListNode(2); ListNode listNode3 = new ListNode(1); ListNode listNode4 = new ListNode(3); listNode1.next=listNode2; listNode2.next=listNode3; listNode3.next=listNode4; ListNode result= new SortList148().sortList(listNode1); while (result!=null){ System.out.println(result.val); result=result.next; } } static class ListNode{ int val; ListNode next; public ListNode(int val){ this.val=val; this.next=null; } public ListNode(int val,ListNode listNode){ this.val=val; this.next=listNode; } public ListNode () { } } public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode fast = head.next, slow = head; while (fast != null && fast.next != null) {//我们选用的方法是双指针法，每次一个指针后移一位，另外一个后移两位。 slow = slow.next; fast = fast.next.next; } ListNode tmp = slow.next;//将此引用指向的对象赋值给tmp引用，让tmp引用也指向此对象，如2->[4->5] slow.next = null;//此引用改变对象的指向，next指向null,2->null ListNode left = sortList(head); ListNode right = sortList(tmp); ListNode h = new ListNode(0); ListNode res = h;//res一直指向0节点,而h则会指向其他节点即其他对象 while (left != null && right != null) { if (left.val < right.val) { h.next = left; left = left.next; } else { h.next = right; right = right.next; } h = h.next; } h.next = left != null ? left : right; return res.next; } }
上述引用和对象的操作有点疑惑，故写如下代码进行测试和验证
public class TestRefDemo { static class Dog{ int val; } public static void main(String[] args) { int a=1; System.out.println("a:"+a); method1(a); System.out.println("a:"+a); Dog dog = new Dog(); dog.val=1; Dog dog1=dog;//dog1和dog引用均指向dog对象，所以修改dog对象，打印两个引用的值均改变 System.out.println("dog:"+dog.val); System.out.println("dog1:"+dog1.val); method(dog); dog=null;//dog引用不再指向dog对象，而是指向了null //System.out.println("dog:"+dog.val);//Exception in thread "main" java.lang.NullPointerException System.out.println("dog1:"+dog1.val); } private static void method1(int a) { a=2;//基本类型超过作用域则不起作用 } private static void method(Dog dog) { dog.val=2;//修改了此引用指向的对象 } }
a:1 a:1 dog:1 dog1:1 dog1:2
解答二：归并排序（迭代法）
递归的时候，并没有做什么特别的事，只是从中间分成两半，每一半自己去做排序，最后合并起来，是后序遍历，从叶子节点往回看：
1. 区间的长度都为1，直接返回，不用合并；
2. 区间的长度为2，两个子区间都排好序了，将它们合并起来；
3. 区间的长度为4，两个子区间都排好序了，将它们合并起来；
4. ……
迭代怎么写？
从上面的分析可以看出，其实只需要枚举步长1,2,4,……，对由每个步长分开的区间，都合并一下。
比如，一开始数组为[8 7 6 5 4 3 2 1]。
第一遍，步长为1，将相邻的两个区间合并（注意加粗黑体）：
7 8 6 5 4 3 2 1
7 8 5 6 4 3 2 1
7 8 5 6 3 4 2 1
7 8 5 6 3 4 1 2
第二遍，步长为2，将相邻的两个区间合并（注意加粗黑体）：
5 6 7 8 3 4 1 2
5 6 7 8 1 2 3 4
第三遍，步长为4，将相邻的两个区间合并（注意加粗黑体）：
1 2 3 4 5 6 7 8
链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-di-gui-die-dai-xiang-jie-by-cherr/
/** * 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) { int length = getLength(head); ListNode dummy = new ListNode(-1); dummy.next = head; for(int step = 1; step < length; step*=2){ //依次将链表分成1块，2块，4块... //每次变换步长，pre指针和cur指针都初始化在链表头 ListNode pre = dummy; ListNode cur = dummy.next; while(cur!=null){ ListNode h1 = cur; //第一部分头 （第二次循环之后，cur为剩余部分头，不断往后把链表按照步长step分成一块一块...） ListNode h2 = split(h1,step); //第二部分头 cur = split(h2,step); //剩余部分的头 ListNode temp = merge(h1,h2); //将一二部分排序合并 pre.next = temp; //将前面的部分与排序好的部分连接 while(pre.next!=null){ pre = pre.next; //把pre指针移动到排序好的部分的末尾 } } } return dummy.next; } public int getLength(ListNode head){ //获取链表长度 int count = 0; while(head!=null){ count++; head=head.next; } return count; } public ListNode split(ListNode head,int step){ //断链操作 返回第二部分链表头 if(head==null) return null; ListNode cur = head; for(int i=1; i<step && cur.next!=null; i++){ cur = cur.next; } ListNode right = cur.next; cur.next = null; //切断连接 return right; } public ListNode merge(ListNode h1, ListNode h2){ //合并两个有序链表 ListNode head = new ListNode(-1); ListNode p = head; while(h1!=null && h2!=null){ if(h1.val < h2.val){ p.next = h1; h1 = h1.next; } else{ p.next = h2; h2 = h2.next; } p = p.next; } if(h1!=null) p.next = h1; if(h2!=null) p.next = h2; return head.next; } } 作者：cherry-n1 链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-di-gui-die-dai-xiang-jie-by-cherr/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解答三：快速排序
public class SingleListQuickSort { static class Node { public int key; public Node next; public Node(int k) { key = k; next = null; } public Node(int k, Node node) { key = k; next = node; } } Node partition(Node begin, Node end) { if(begin == end) return begin; int key = begin.key; Node pNode = begin; Node qNode = begin.next; while(qNode != end) { if(qNode.key < key) { pNode = pNode.next; int tempKey = pNode.key; pNode.key = qNode.key; qNode.key = tempKey; } qNode = qNode.next; } int temp = begin.key; begin.key = pNode.key; pNode.key = temp; return pNode; } void quickSort(Node head, Node end) { if(head != end) { Node pNode = partition(head, end); quickSort(head, pNode); quickSort(pNode.next, end); } } void printSingleList(Node head) { while(head != null) { System.out.println(head.key); head = head.next; } } public static void main(String[] args) { Node head = new Node(4); Node node = new Node(2); Node node2 = new Node(5); Node node3 = new Node(3); Node node4 = new Node(7); Node node5 = new Node(9); Node node6 = new Node(0); Node node7 = new Node(1); head.next = node; node.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node7; SingleListQuickSort singleListQuickSort = new SingleListQuickSort(); singleListQuickSort.quickSort(head, null); singleListQuickSort.printSingleList(head); } }
另附对数组归并排序的代码：
import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] arr = new int[]{4,1,3,2,7,5,8,0,100}; System.out.println("排序前："+Arrays.toString(arr)); int[] resultArr= mergeSort(arr); System.out.println("排序后："+Arrays.toString(resultArr)); } /** * 归并排序 * @param arr * @return */ private static int[] mergeSort(int[] arr) { int arrLength; if(arr==null || (arrLength=arr.length)<2 ){ return arr; } int halfSize = arrLength/2; int[] left = Arrays.copyOfRange(arr,0,halfSize); int[] right = Arrays.copyOfRange(arr,halfSize,arrLength); return merge(mergeSort(left),mergeSort(right)); } /** * 对两个已经排好序的子数组进行合并排序 * @param mergeSortLeft * @param mergeSortRight * @return */ private static int[] merge(int[] mergeSortLeft, int[] mergeSortRight) { checkArgs(mergeSortLeft,mergeSortRight); int[] results = new int[mergeSortLeft.length+mergeSortRight.length];//非空判断 int m=0;//指向left的索引 int n=0;//指向right的索引 for (int i = 0; i < results.length; i++) { if(m>=mergeSortLeft.length){ results[i]=mergeSortRight[n];// n++; }else if(n>=mergeSortRight.length){ results[i]=mergeSortLeft[m];// m++; }else if(mergeSortLeft[m]<=mergeSortRight[n]){ results[i]=mergeSortLeft[m];// m++; }else if(mergeSortLeft[m]>mergeSortRight[n]){ results[i]=mergeSortRight[n];// n++; } } return results; } private static int[] checkArgs(int[] mergeSortLeft, int[] mergeSortRight) { int[] result = null; // if (mergeSortLeft==null || mergeSortLeft.length==0){ // if(mergeSortRight==null || mergeSortRight.length==0){ // result= null; // }else { // result=mergeSortRight; // } // } return result; } }
另附对数组快速排序的代码：
import java.util.Arrays; public class QuickSortArray1 { public static void main(String[] args) { int[] arr = {8, 1, 3, 2, 7, 6, 4}; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } private static void quickSort(int[] arr, int start, int end) { if (arr == null || arr.length <= 1 || start < 0 || end >= arr.length || start >= end || end < 0) { return; } int mid = partion(arr, start, end); quickSort(arr, start, mid - 1); quickSort(arr, mid + 1, end); } private static int partion(int[] arr, int start, int end) { int key = arr[end]; int left = start - 1; for (int i = start; i <= end; i++) { if (arr[i] <= key) { left++; if (i > left) { int tmp = arr[left]; arr[left] = arr[i]; arr[i] = tmp; } } } return left; } }