NC70：单链表的排序/LeetCode：148.排序链表
单链表的排序
https://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08?tpId=196&&tqId=37150&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
LC 148.排序链表：https://leetcode-cn.com/problems/sort-list/
解法一：值排序
思路
直接遍历整个链表，用一个数组存储所有的val，然后进行排序，最后将排序完的值赋值给链表
实现代码
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类 the head node
* @return ListNode类
*/
public ListNode sortInList (ListNode head) {
// write code here
if(head == null)
return head;
ListNode p = head;
ListNode q = head;
ListNode t = head;
int n = 0;
while(p != null){//获得链表元素数量
n++;
p = p.next;
}
int[] arr = new int[n];
for(int i = 0; i<n; i++){//新建一个数组存储链表的值
arr[i] = head.val;
head = head.next;
}
Arrays.sort(arr);
int i = 0;
while(q != null){//将排序好的数组赋值给链表
q.val = arr[i++];
q = q.next;
}
return t;//返回新的表头
}
} 解法二：归并排序
思路
两个核心操作是分治和将两个有序序列合并成一个有序序列（无论这个序列是顺序存储还是链式存储），即（递归+合并）
实现代码
/**
* 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 || head.next == null){
return head;
}
//快慢指针求中点
ListNode h1 = head;
ListNode h2 = head.next;
while(h2 != null && h2.next != null){
h1 = h1.next;
h2 = h2.next.next;
}
ListNode left = head; //以head到中点h1为左链表
ListNode right = h1.next; //右链表
h1.next = null; //左链表为一个单独的链表，需要将尾节点指向null
//递归分治
ListNode lHead = sortList(left);
ListNode rHead = sortList(right);
//合并两个有序链表
ListNode newNode = new ListNode(-1); //辅助头节点
ListNode pre = newNode;
while(lHead != null && rHead != null){
if(lHead.val < rHead.val){
newNode.next = lHead;
lHead = lHead.next;
}else{
newNode.next = rHead;
rHead = rHead.next;
}
newNode = newNode.next;
}
//判断链表是否为空，不为空直接接上
newNode.next = lHead != null ? lHead : rHead;
return pre.next;
}
} 
