腾讯&leetcode148：排序链表 #79

Activity

1. sisterAn

   added

   LeetCode

   腾讯

   on Jul 6, 2020
2. sisterAn commented on Jul 6, 2020

   

   sisterAn

   on Jul 6, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解答：采用归并排序

   归并排序采用了分治策略，将数组分成2个较小的数组，然后每个数组再分成两个更小的数组，直至每个数组里只包含一个元素，然后将小数组不断的合并成较大的数组，直至只剩下一个数组，就是排序完成后的数组序列。

   对应于链表喃？

   4->2->1->3

   第一步：分割

   

   • 使用快慢指针（双指针法），获取链表的中间节点
   • 根据中间节点，分割成两个小链表
   • 递归执行上一步，直到小链表中只有一个节点

   第二步：归并（合并有序链表）

   

   代码实现

   let sortList = function(head) {
       return mergeSortRec(head)
   }
   
   // 归并排序
   // 若分裂后的两个链表长度不为 1，则继续分裂
   // 直到分裂后的链表长度都为 1，
   // 然后合并小链表
   let mergeSortRec = function (head) {
       if(!head || !head.next) {
           return head
       }
   
       // 获取中间节点
       let middle = middleNode(head)
       // 分裂成两个链表
       let temp = middle.next
       middle.next = null
       let left = head, right = temp
       // 继续分裂（递归分裂）
       left = mergeSortRec(left)
       right = mergeSortRec(right)
       // 合并两个有序链表
       return mergeTwoLists(left, right)
   }
   
   // 获取中间节点
   // - 如果链表长度为奇数，则返回中间节点
   // - 如果链表长度为偶数，则有两个中间节点，这里返回第一个
   let middleNode = function(head) {
       let fast = head, slow = head
       while(fast && fast.next && fast.next.next) {
           slow = slow.next
           fast = fast.next.next
       }
       return slow
   }
   
   // 合并两个有序链表
   let mergeTwoLists = function(l1, l2) {
       let preHead = new ListNode(-1);
       let cur = preHead;
       while(l1 && l2){
           if(l1.val < l2.val){
               cur.next = l1;
               l1 = l1.next;
           }else{
               cur.next = l2;
               l2 = l2.next;
           }
           cur = cur.next;
       }
       cur.next = l1 || l2;
       return preHead.next;
   }

   引入递归算法的复杂度分析：

   • 递归算法的时间复杂度：递归的总次数 * 每次递归的数量
   • 递归算法的空间复杂度：递归的深度 * 每次递归创建变量的个数

   复杂度分析

   • 时间复杂度：递归的总次数为 T(logn) ，每次递归的数量为 T(n) ，时间复杂度为 O(nlogn)
   • 空间复杂度：递归的深度为 T(logn) ，每次递归创建变量的个数为 T(c) （c为常数），空间复杂度为 O(logn)

   关于复杂度分析，请看这篇：前端进阶算法1：如何分析、统计算法的执行效率和资源消耗？

   优化递归

   使用迭代代替递归，优化时间复杂度：O(logn) —> O(1)

   今天太晚了，明日更新🤦‍♀️

   😄React with 😄4Reacted by 瓶子君, cs739295, Miss Chen and chuck
3. jasonting5 commented on Jul 7, 2020

   

   jasonting5

   on Jul 7, 2020

   More actions

   先递归后合并

   var sortList = function(head) {
       if (!head || !head.next) {
           return head
       }
       let slow = head, fast = head.next
       while (fast && fast.next) {
           slow = slow.next
           fast = fast.next
       }
       let tmp = slow.next
       slow.next = null
       let left = head
       let right = tmp
       left = sortList(left)
       right = sortList(right)
       return merge(left, right)
   };
   function merge (left,right) {
       let p1 = left, p2 = right, res = new ListNode(0), tick = res
       while (p1 && p2) {
           if (p1.val < p2.val) {
               tick.next = p1
               p1 = p1.next
           } else {
               tick.next = p2
               p2 = p2.next
           }
           tick = tick.next
       }
       tick.next = p1 ? p1 : p2
       return res.next
   }
4. cutie6 commented on Jan 6, 2021

   

   cutie6

   on Jan 6, 2021

   More actions

    let preHead = new ListNode(-1);

   这里 ListNode 的类定义方便给一下嘛？
5. Jet12138 commented on Sep 11, 2022

   

   Jet12138

   on Sep 11, 2022

   More actions

    let preHead = new ListNode(-1);

   这里 ListNode 的类定义方便给一下嘛？

   /**

   • Definition for singly-linked list.
   • function ListNode(val, next) {

   • this.val = (val===undefined ? 0 : val)
     

   • this.next = (next===undefined ? null : next)
     

   • }
     */

   leetcode题目作答那里有。 以后碰到leetcode的链表题目，ListNode的结构都是这个构造函数，它主要用实例化链表节点对象。