NC单链表的排序

系列文章目录

前言

前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。

描述
给定一个节点数为n的无序单链表，对其按升序排序。

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 hereif (head == null || head.next == null)return head;// 使用快慢指针寻找链表的中点ListNode fast = head.next, slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}ListNode tmp = slow.next;slow.next = null;// 递归左右两边进行排序ListNode left = sortInList(head);ListNode right = sortInList(tmp);// 创建新的链表ListNode h = new ListNode(0);ListNode res = h;// 合并 left right两个链表while (left != null && right != null) {// left  right链表循环对比if (left.val < right.val) {h.next = left;left = left.next;} else {h.next = right;right = right.next;}h = h.next;}// 最后添加未对比的链表部分判断左链表是否为空h.next = left != null ? left : right;return res.next;}
}