题解 | #牛牛的链表排序#

import java.util.*;

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
      public ListNode sortLinkedList(ListNode head) {
        // 如果头结点为空，或者只有一个节点，那么直接返回头结点
        if (head == null || head.next == null) {
            return head;
        }
        ListNode middle = findMiddle(head);
        ListNode middleNext = middle.next;
        // 将中间链表断开
        middle.next = null;
        // 分别递归左右链表
        ListNode sortLinkedList1 = sortLinkedList(head);
        ListNode sortLinkedList2 = sortLinkedList(middleNext);
        // 合并链表
        return merge(sortLinkedList1, sortLinkedList2);
    }

    private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode merge(ListNode listNode1, ListNode listNode2) {
        ListNode cur = new ListNode(-1);
        ListNode result = cur;
        while (listNode1 != null && listNode2 != null) {
            if (listNode1.val < listNode2.val) {
                cur.next = listNode1;
                listNode1 = listNode1.next;
            } else {
                cur.next = listNode2;
                listNode2 = listNode2.next;
            }
            cur = cur.next;
        }
        if(listNode1!=null){
            cur.next = listNode1;
        }
        if(listNode2!=null){
            cur.next = listNode2;
        }
        return result.next;
    }
  // 方法二：将链表排序转到集合中，用API做，但是很可能面试官考的就是让你用归并排序，用方法二的话，基本上学过算法的都会做，有点投机取巧。
    public ListNode sortLinkedList (ListNode head) {
        // write code here
        if(head==null||head.next==null) return head;
        ArrayList<Integer> l = new ArrayList<>();
        ListNode node = head;
        while(node!=null){
            l.add(node.val);
            node = node.next;
        }
        Collections.sort(l); //排序
        node = head; //重新指回头节点
        for(int i=0; i<l.size(); i++){
            node.val = l.get(i); //赋值
            node = node.next;
        }
        return head;
    }
}

本题知识点分析：

1.归并排序

2.链表合并

3.数学模拟

本题解题思路分析：

1.利用归并排序，和数组差不多的形式，无非是链表需要找中间节点还有合并有序链表，其他都差不多

2.归并排序，分治思想，分别递归左右链表，然后合并已经排序的有序链表返回

本题使用编程语言: Java

如果你觉得本篇文章对你有帮助的话， 可以点个赞支持一下，感谢~