1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84  // @Title: 排序链表 (Sort List) // @Author: 15816537946@163.com // @Date: 2019-11-07 18:31:54 // @Runtime: 8 ms // @Memory: 4.9 MB /* * @lc app=leetcode.cn id=148 lang=golang * * [148] 排序链表 * * https://leetcode-cn.com/problems/sort-list/description/ * * algorithms * Medium (61.57%) * Likes: 256 * Dislikes: 0 * Total Accepted: 21.2K * Total Submissions: 34.3K * Testcase Example: '[4,2,1,3]' * * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 * * 示例 1: * * 输入: 4->2->1->3 * 输出: 1->2->3->4 * * * 示例 2: * * 输入: -1->5->3->4->0 * 输出: -1->0->3->4->5 * */ /** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ // 归并排序 func sortList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } slow := head fast := head.Next for fast != nil && fast.Next != nil { slow, fast = slow.Next, fast.Next.Next } // 1. 断链 mid := slow.Next slow.Next = nil // 2. 切割 left := sortList(head) right := sortList(mid) header := new(ListNode) cursor := header // 3. 合并 for left != nil && right != nil { if left.Val > right.Val { cursor.Next, right = right, right.Next } else { cursor.Next, left = left, left.Next } cursor = cursor.Next } if left != nil { cursor.Next = left } else { cursor.Next = right } return header.Next }