题解 | #单链表的排序#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null) {
            return head;
        }
        ArrayList<Integer> array = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            array.add(p.val);
            p=p.next;
        }
        p=head;
        Collections.sort(array);
        for (int i = 0; i < array.size(); ++i) {
            p.val=array.get(i);
            p=p.next;
        }
        return head;
    }
}

方法一：转换为数组，利用数组内置的排序方法排序

1.遍历链表将元素添加到数组中

2.调用Java 的Collections 类的静态方法 sort() 可以对集合中的元素进行升序排序。

3.依次将元素值赋值给每个链表结点即可

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode merge(ListNode pHead1,ListNode pHead2){
        if(pHead1==null){
            return pHead2;
        }
        if(pHead2==null){
            return pHead1;
        }
        ListNode head=new ListNode(0);
        ListNode cur = head;
        while(pHead1!=null&&pHead2!=null){
            if(pHead1.val<pHead2.val){
                cur.next=pHead1;
                pHead1=pHead1.next;
            }else{
                cur.next=pHead2;
                pHead2=pHead2.next;
            }
            cur=cur.next;
        }
        if(pHead1!=null){
            cur.next=pHead1;
        }else{
            cur.next=pHead2;
        }
        return head.next;
    }
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null||head.next==null) {
            return head;
        }
        ListNode right=head.next.next;
        ListNode mid=head.next;
        ListNode left=head;
        while(right!=null&&right.next!=null){
            right=right.next.next;
            mid=mid.next;
            left=left.next;
        }
        left.next=null;
        //分成两段，递归，达到递归出口后会调用自己编写的merge函数  
        return merge(sortInList(head),sortInList(mid));
    }
}

方法二：归并排序

利用分治和双指针思想，将链表从中间不断拆分，直到链表只剩一个结点或为空，再两两合并，使用递归实现。

1.首先，编写好两个有序链表合并的代码

2.设置递归出口条件：head == null || head.next==null

3.使用快慢指针找到链表中间断开（当快指针到达链表末尾时慢指针指向链表中间），注意要有一个指向慢指针的指针

4.向下递归：将头结点head和慢指针mid分别调用所在的本函数进行递归，并作为合并函数merge的两个参数。