Java版《单链表排序》

1. 值排序，不是真正做到链表排序，直接遍历整个链表，用一个数组存储所有的val，然后进行排序，最后将排序完的值赋值给链表

   import java.util.*;
   public class Solution {
   
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head == null || head.next == null)
            return head;
        ArrayList<Integer> list = new ArrayList<>();
        ListNode tmp = head;
        while(tmp != null){
            list.add(tmp.val);
            tmp = tmp.next;
        }
        list.sort((a,b)->{return a-b;});
        ListNode temp = head;
        int i = 0;
        while(temp != null){
            temp.val = list.get(i++);
            temp = temp.next;
        }
        return head;
    }
   }

2. 归并排序
   思路：先利用快慢指针找出链表的中点，然后分为两个链表，一直分，知道无法分为止，然后自底而上排序归并

import java.util.*;
public class Solution {
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head == null || head.next == null)
            return head;
        //使用快慢指针找到中点
        ListNode slow = head, fast = head.next;
        while(fast!=null && fast.next !=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //分割为两个链表
        ListNode newList = slow.next;
        slow.next = null;
        //将两个链表继续分割
        ListNode left = sortInList(head);
        ListNode right = sortInList(newList);

        ListNode lhead = new ListNode(-1);
        ListNode res = lhead;
        //归并排序
        while(left != null && right != null){
            if(left.val < right.val){
                lhead.next = left;
                left = left.next;
            }else{
                lhead.next = right;
                right = right.next;
            }
            lhead = lhead.next;
        }
        //判断左右链表是否为空
        lhead.next = left!=null?left:right;
        return res.next;
    }
}