企业官网建设流程全解析

题目

给你链表的头结点head，请将其按升序排列并返回排序后的链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目在范围[0, 5 * 104]内
• -105 <= Node.val <= 105

进阶：你可以在O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序吗？

题解

/** * 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 slow = head, fast = head.next; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } ListNode mid = slow.next; slow.next = null; // 切断链表，分成前后两段 ListNode left = sortList(head); ListNode right = sortList(mid); //合并 return merge(left, right); } // 合并两个有序链表 private ListNode merge(ListNode l1, ListNode l2){ ListNode dummy = new ListNode(-1); ListNode cur = dummy; while(l1 != null && l2 != null){ if(l1.val < l2.val){ cur.next = l1; l1 = l1.next; }else{ cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dummy.next; } }

思路

（递归归并）

1. 快慢指针找链表中点，分割成左右两段
2. 递归分别排序左、右
3. 合并两个有序链表