力扣第148、179题

148.排序链表

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

归并排序

思路：

  1. 将链表分成两个子链表
  2. 对两个子链表排序后再将它们合并成一个排序的链表 ```javascript var sortList = function (head) { if (!head || !head.next) return head; let slow = head, fast = head; let preSlow = null; while (fast && fast.next) {
    1.  preSlow = slow;
    2.  slow = slow.next;
    3.  fast = fast.next.next;
    } preSlow.next = null; const l = sortList(head); const r = sortList(slow); return merge(l, r); };

function merge(l1, l2) { const dummy = new ListNode(0); let prev = dummy; while (l1 && l2) { if (l1.val < l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } if (l1) prev.next = l1; if (l2) prev.next = l2; return dummy.next; }

  1. 时间复杂度是 O(nlogn)<br />空间复杂度是 O(logn)
  2. <a name="RaHS5"></a>
  3. ## 179.最大数
  4. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22950280/1642003650579-9d037a98-506c-4c08-b08a-a3315d5a67b5.png#clientId=u69916d6f-e94c-4&from=paste&height=455&id=u1f149bb2&margin=%5Bobject%20Object%5D&name=image.png&originHeight=606&originWidth=562&originalType=binary&ratio=1&size=26938&status=done&style=shadow&taskId=u2e3c91e6-2976-4914-abd2-e0beac163b0&width=422)
  5. <a name="YsNQo"></a>
  6. ### 自定义排序
  8. - 做一个特殊的降序排列 a + b 与 b + a 比较 (类型隐式转换)
  10. 思路：
  12. 1. 把两个数字a、b合起来，比较ab和ba的大小，取大的
  13. 1. 按自定义规则，降序排序
  15. 简洁代码
  16. ```javascript
  17. var largestNumber = function(nums) {
  18.     const res = nums.sort((a, b) =>  (b + '' + a) - (a + '' + b)).join('')
  19.     return res.startsWith('0') ? '0' : res
  20.       //处理元素全为0的情况
  21. };

or

  1. var largestNumber = function(nums) {
  2.     nums = nums.sort((a, b) => {
  3.         let S1 = `${a}${b}`;
  4.         let S2 = `${b}${a}`;
  5.         return S2 - S1;
  6.     });
  7.     return nums[0] ? nums.join('') : '0';
  8. };