lc148链表排序——链表版归并排序

148. 排序链表 - 力扣（LeetCode）

法1：递归版归并排序

/*** 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)return head;return mergeSort(head);}public ListNode mergeSort(ListNode head) {//仅1个元素了if(head.next == null)return head;//快慢指针，且拆成2半ListNode secondHead = getSecondHead(head);head = mergeSort(head);secondHead = mergeSort(secondHead);return merge(head, secondHead);}//合并两个有序链表public ListNode merge(ListNode head, ListNode secondHead) {// 哑结点技巧ListNode dummyHead = new ListNode();ListNode curNode = dummyHead;while(head != null && secondHead != null) {if(head.val <= secondHead.val) {curNode.next = head;head = head.next;} else {curNode.next = secondHead;secondHead = secondHead.next;}//艹，忘了更新curNodecurNode = curNode.next;}//如果head先为空if(head == null)curNode.next = secondHead;else curNode.next = head;return dummyHead.next;}//快慢指针获取另一半首节点,前面已经检验至少2个节点,并且要断开为2个链表public ListNode getSecondHead(ListNode head) {//初始化ListNode slow = head;ListNode fast = head.next;while(fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}//注意必须要断成2节head = slow.next;slow.next = null;return head;}
}

空间复杂度为递归栈空间，logn，因为链表特性不像数组版标准归并排序，还需要O(n)的额外数组来合并2个旧数组。

法2：迭代版归并排序

递归是要自顶向下进行分治，一分二，二分四......它是自顶往下调用的，虽然计算仍然是从下往上计算得出然后返回的。

但可以直接用自底向上的思想，直接先从底部计算，再往上“累积”，避开了自顶向下调用的过程。但实现就要麻烦很多。

/*** 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) {// 16.19if(head == null || head.next == null)return head;//获取长度int n = getLen(head);ListNode dummyHead = new ListNode(0, head);ListNode curNode;ListNode preLinkLast;ListNode[] heads;ListNode head1, head2;//step是每次合并的两链表的长度for(int step = 1; step < n; step *= 2) {curNode = dummyHead.next;preLinkLast = dummyHead;//2个2个的合并while(curNode != null) {head1 = curNode;// splitList方法，是获取head开头的长step的链表，// 并将其与后面断开，且返回断开后的下一个链表头head2 = splitList(head1, step);//下一轮迭代的headcurNode = splitList(head2, step);//合并2个有序链表，并返回合并的链表头和尾heads = mergeTwoLists(head1, head2);preLinkLast.next = heads[0];preLinkLast = heads[1];}}return dummyHead.next;}//返回链表总长度public int getLen(ListNode head) {int cnt = 0;while(head != null) {cnt++;head  = head.next;}return cnt;}//或取head开头长step的链表，并将其与后面断开// 并返回断开后的head// 若长度不到step，返回nullpublic ListNode splitList(ListNode head, int step) {int cnt = 1;while(head != null && cnt < step) {head = head.next;cnt++;}if(head == null)return null;ListNode nextHead = head.next;head.next = null;return nextHead;}// 合并2个有序链表，并返回新的合并后的head和tailpublic ListNode[] mergeTwoLists(ListNode head1, ListNode head2){ListNode dummyHead = new ListNode();ListNode curNode = dummyHead;while(head1 != null && head2 != null) {if(head1.val <= head2.val) {curNode.next = head1;head1 = head1.next;}else {curNode.next = head2;head2 = head2.next;}curNode = curNode.next;}if(head1 == null)curNode.next = head2;else curNode.next = head1;while(curNode.next != null) {curNode = curNode.next;}return new ListNode[]{dummyHead.next, curNode};}
}

TIP：当方法需要返回2个节点时，不一定就用内部类，用数组ListNode[]也行，还能简化些和更清晰些。

TIP：当需要很多局部变量时，可以先循环内定义把逻辑写完，后面再优化提出到循环外定义，直接一开始就把所有变量定义好比较难想，而且容易昏乱

TIP：这里不要采用快慢指针求双链表了，而是用splitList方法，取之后step长的链表并断开，用快慢指针逻辑会变复杂，又要返回断开后2个链表的头，还要返回下一轮迭代链表的头，还要考虑链表长度在0-step,step-2step, >2step几种情况，太烦了。

还是递归好，迭代写起来还挺麻烦的，而且logn空间复杂度其实非常低，n = 1百万时 logn才20，1亿时logn也就26.57左右，其实相比之下还是非常小的。