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 || 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下个节点置空 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; } }
解题思想:快慢指针确定中间值,递归分割链表为子序列,然后进行归并排序,最后赋值无需排序的剩余节点。