【Check 44】2024-04-04 - 148. 排序链表

[larscheng]

148. 排序链表

[larscheng]

思路

• 方法一：收集节点到数组，进行排序，重新构建升序链表，此方法空间复杂度O(n)
• 方法二：归并排序，递归实现，此方法空间复杂度O(n)

• 方法三：归并排序，迭代实现，此方法空间复杂度O(1)，时间复杂度位O(nlogn)

  代码

  
  class Solution {
  public ListNode sortList(ListNode head) {
      int length = getLength(head);
      //从最小子集开始，两两合并
      int subLen = 1;
      ListNode dummy = new ListNode(0,head);
      while (subLen<length){
          //第一层循环：从最小子集subLen=1，2，4...开始两两合并
          ListNode pre = dummy;
          ListNode cur = dummy.next;
  
          while (cur!=null){
              //第一段头节点
              ListNode h1 = cur;
              //第二段头节点
              ListNode h2 = spiltList(h1, subLen);
              //下一轮起点
              cur = spiltList(h2,subLen);
              //下一轮pre
              pre = mergeList(h1, h2, pre);
          }
          subLen*=2;
      }
      return dummy.next;
  }
  
  private ListNode mergeList(ListNode h1, ListNode h2, ListNode pre) {
      //类似合并两个有序链表
      while (h1 != null && h2 != null) {
          if (h1.val < h2.val) {
              pre.next = h1;
              h1 = h1.next;
          } else {
              pre.next = h2;
              h2 = h2.next;
          }
          pre = pre.next;
      }
      if (h1 == null) {
          pre.next = h2;
      }
      if (h2 == null) {
          pre.next = h1;
      }
      while (pre.next!=null){
          pre = pre.next;
      }
      return pre;
  }
  
  private ListNode spiltList(ListNode h1, int subLen) {
      //找下一段的头节点
      if (h1==null){
          return null;
      }
      ListNode temp = h1;
      for (int i = 1; i < subLen; i++) {
          if (temp==null){
              return null;
          }else {
              temp = temp.next;
          }
      }
      if (temp == null) {
         return null;
      }
      ListNode next = temp.next;
      temp.next = null;
      return next;
  }
  
  private int getLength(ListNode head) {
      int length = 0;
      ListNode cur = head;
      while (cur!=null){
          cur = cur.next;
          length++;
      }
      return length;
  }
  }