链表|148. 排序链表

148. 排序链表

题目：给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。

题目链接： 148. 排序链表
时间复杂度：快排 O(n^2) 超出时间限制

class Solution {public ListNode sortList(ListNode head) {if(head==null){return head;}ListNode dummy=new ListNode(Integer.MIN_VALUE,null);ListNode pointnew=dummy;ListNode pointold=head;while(pointold!=null){while(pointnew!=null&&pointnew.next!=null){if(pointold.val<=pointnew.next.val){ListNode next=pointnew.next;ListNode node=new ListNode(pointold.val);pointnew.next=node;node.next=next;pointnew=dummy;break;}else{pointnew=pointnew.next;}}if(pointnew.next==null){ListNode next=pointnew.next;ListNode node=new ListNode(pointold.val);pointnew.next=node;node.next=next;pointnew=dummy;}pointold=pointold.next;}return dummy.next;}
}

归并排序O(logn)：

class Solution {public ListNode sortList(ListNode head) {if(head==null||head.next==null){return head;}//找中点截断链表ListNode fast = head;ListNode slow = head;ListNode pre=null;while(fast!=null&&fast.next!=null){pre=slow;slow=slow.next;fast=fast.next.next;}//递归截断链表pre.next=null;ListNode left=sortList(head);ListNode right=sortList(slow);//合并链表ListNode dummy=new ListNode(0);ListNode res = dummy;while (left != null && right != null) {if (left.val < right.val) {res.next = left;left = left.next;} else {res.next = right;right = right.next;}res=res.next;}res.next=left!=null?left:right;return dummy.next;}
}

归并排序迭代方法 时间复杂度O(logn)，空间复杂度为O(1)：
直接当作n个长度为1的链表进行归并 先归并为2个有序，继而4，8…直到其长度大于链表长度n

public ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}// 获取链表长度int length = 0;ListNode current = head;while (current != null) {length++;current = current.next;}ListNode dummy = new ListNode(0);dummy.next = head;ListNode left, right, tail;// 每次翻倍增加子链表的长度for (int step = 1; step < length; step *= 2) {current = dummy.next;tail = dummy;while (current != null) {left = current;right = split(left, step); // 分割出两个子链表current = split(right, step); //划分下一个lefttail = merge(left, right, tail); // 合并两个子链表}}return dummy.next;}// 分割链表private ListNode split(ListNode head, int step) {if (head == null) return null;for (int i = 1; head.next != null && i < step; i++) {head = head.next;}ListNode right = head.next;head.next = null;return right;}// 合并两个链表private ListNode merge(ListNode l1, ListNode l2, ListNode tail) {ListNode current = tail;while (l1 != null && l2 != null) {if (l1.val < l2.val) {current.next = l1;l1 = l1.next;} else {current.next = l2;l2 = l2.next;}current = current.next;}current.next = (l1 != null) ? l1 : l2;while (current.next != null) {current = current.next;}return current;}