LeetCode Hot 热题100 算法题 148.排序链表-算法&测试-medium模式

给你链表的头结点head，请将其按升序排列并返回排序后的链表。
进阶：你可以在O(nlogn)时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例：head=[4,2,1,3]
输出：[1,2,3,4]
思路：归并排序

package leetcode.medium;

//148.排序链表
public class Solution148 {
	public static void main(String[] args) {
		ListNode head=new ListNode(4);
		head.next=new ListNode(2);
		head.next.next=new ListNode(1);
		head.next.next.next=new ListNode(3);
		System.out.println("before sort:");
		ListNode curr=head;
		while(curr!=null) {
			System.out.println("=>"+curr.val);
			curr=curr.next;
		}
		
		S148SortList testSortList = new S148SortList();
		System.out.println("after sort:");
		ListNode cur = testSortList.sortList(head);
		while(cur!=null) {
			System.out.println("=>"+cur.val);
			cur=cur.next;
		}
	}
}

class S148SortList{
	//override
	public ListNode sortList(ListNode head) {
		return sortList(head, null);
	}
	//方法148：将一个链表升序排序并返回
	public ListNode sortList(ListNode head,ListNode tail) {
		//递归终止条件：节点数<=1，不再需要拆分或排序
		if (head==null) {
			return head;
		}
		if (head.next==tail) {
			head.next=null;//取出该节点
			return head;
		}
		
		//1.快慢指针找出链表的中点：
		//fast每次移动2步，slow每次移动1步，当fast到达末尾时，slow所指节点即链表中点
		ListNode slow=head;
		ListNode fast=head;
		while(fast!=tail) {
			slow=slow.next;
			fast=fast.next;
			if (fast!=tail) {
				fast=fast.next;
			}
		}		
		ListNode mid=slow;
		
		//2.向左向右递归分解，对两个子链表分别排序
		ListNode list1=sortList(head, mid);//tail即mid不参与list1的排序
		ListNode list2=sortList(mid, tail);//tail不参与list2排序
		
		//3.合并两个有序链表
		ListNode sortedList=mergeList(list1, list2);
		return sortedList;
	}
	
	//方法21：合并两个有序链表
	public ListNode mergeList(ListNode head1,ListNode head2) {
		ListNode newHead = new ListNode(-1);
		ListNode nh = newHead;
		ListNode h1=head1;
		ListNode h2=head2;
		while(h1!=null && h2!=null) {
			if (h1.val<=h2.val) {
				nh.next=h1;
				h1=h1.next;
			}else {
				nh.next=h2;
				h2=h2.next;
			}
			nh=nh.next;
		}
		if (h1==null) {
			nh.next=h2;
		}else {
			nh.next=h1;
		}
		return newHead.next;
	}
}

参考：
https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution