文章

Leetcode-148-排序链表📌

Algorithm

Leetcode-148-排序链表📌

Leetcode-148-排序链表📌

148. 排序链表

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

示例 1:

img

输入:head = [4,2,1,3]
输出:[1,2,3,4]

示例 2:

img

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

解题思路

这道题思路还是很清晰,只不过整体代码量较多,使用到的是归并排序思想。

function sortList(head: ListNode | null): ListNode | null {
  // 边界判断
  if (head === null || head.next === null) {
    return head;
  }
 
  // 找出中间节点
  let mid = findMiddleNode(head);
 
  // 将链表拆分成左右两个链表,记得断链
  let left = head;
  let right = mid.next;
  mid.next = null;
 
  // 递归排序左右链表
  let leftHead = sortList(left);
  let rightHead = sortList(right);
 
  // 合并两个有序链表
  let mergeHead = mergeTwoLinkedList(leftHead, rightHead);
 
  return mergeHead;
 
  // 找出链表的中间结点,如果链表的个数是偶数,则返回中间节点的第一个节点
  function findMiddleNode(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) {
      return head;
    }
 
    let slow = head;
    let fast = head;
 
    while (fast.next !== null && fast.next.next !== null) {
      slow = slow.next;
      fast = fast.next.next;
    }
 
    return slow;
  }
 
  // 合并两个有序的链表
  function mergeTwoLinkedList(
    list1: ListNode | null,
    list2: ListNode | null
  ): ListNode | null {
    // dummyHead
    let list3 = new ListNode(-1);
    let temp = list3;
 
    while (list1 !== null && list2 !== null) {
      if (list1.val <= list2.val) {
        temp.next = list1;
        list1 = list1.next;
      } else {
        temp.next = list2;
        list2 = list2.next;
      }
      temp = temp.next;
    }
 
    temp.next = list1 === null ? list2 : list1;
 
    return list3.next;
  }
}