物联网小项目/seo零基础入门到精通200讲

题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

解题思路

1、题意理解：要求常数级空间复杂度，所以不能创建辅助空间
2、初步想法，用原地归并排序对链表进行排序
3、对代码1的理解：
（1）用快慢指针将链表分成两部分，通过prev.next = null将链表断开
（2）分别对前半段和后半段链表进行排序
（3）将两个排好序的链表合并。

代码1

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode sortList(ListNode head) {if(head == null || head.next == null){return head;}ListNode prev = null, slow = head, fast = head;while(fast != null && fast.next != null){prev = slow;slow = slow.next;fast = fast.next.next;}prev.next = null;ListNode l1 = sortList(head);ListNode l2 = sortList(slow);return merge(l1, l2);}ListNode merge(ListNode l1, ListNode l2){ListNode l = new ListNode(0), p = l;while(l1 != null && l2 != null){if(l1.val < l2.val){p.next = l1;l1 = l1.next;}else{p.next = l2;l2 = l2.next;}p = p.next;}if(l1  != null)p.next = l1;if(l2 != null)p.next = l2;return l.next;}
}

参考：https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/