leetcode hot100【LeetCode 148. 排序链表】java实现

LeetCode 148. 排序链表

题目描述

在 O(nlogn) 的时间复杂度内，对链表进行排序。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目 n 在范围 [0, 5 * 10^4] 内
• 0 <= Node.val <= 5 * 10^4

Java 实现解法

方法：归并排序

/**
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode mid = getMid(head);ListNode rightHalf = mid.next;mid.next = null;ListNode left = sortList(head);ListNode right = sortList(rightHalf);return mergeSort(left, right);}private ListNode getMid(ListNode head) {ListNode fast = head, slow = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}private ListNode mergeSort(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);ListNode curr = dummy;while (l1 != null && l2 != null) {if (l1.val < l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}curr.next = (l1 != null) ? l1 : l2;return dummy.next;}
}

解题思路

• 归并排序：这是一种分治算法，它将链表分成两半，对每半进行排序，然后将排序后的两半合并。
  • 分解：使用 getMid 函数找到链表的中间节点，将链表分成两半。
  • 解决：对两半链表递归地进行排序。
  • 合并：使用 mergeSort 函数合并两个已排序的链表。
    getMid 函数使用快慢指针法找到链表的中间节点。快指针 fast 每次移动两步，慢指针 slow 每次移动一步。当快指针到达链表末尾时，慢指针将位于中间位置。
    merge 函数合并两个已排序的链表。它使用一个虚拟头节点 dummy 和一个指针 curr 来简化合并过程。在循环中，比较两个链表的头节点，将较小的节点链接到 curr 后面，然后移动对应的链表指针和 curr 指针。

这种方法的时间复杂度是 O(nlog n)，空间复杂度是 O(log n)，因为递归栈的深度最多为链表长度的对数。这种方法是排序链表的标准方法，它利用了归并排序的优势来实现高效的排序。

注：题目来源leetcode网站