148. 排序链表

题目描述

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

示例 1：

输入：head = [4,2,1,3]

输出：[1,2,3,4]

示例 2：

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

输出：[-1,0,3,4,5]

示例 3：

输入：head = []

输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 10^4] 内
• -10^5 <= Node.val <= 10^5
• 题目数据保证链表已经按 val 值 非递减顺序 排序

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

出处：LeetCode

解法一：归并排序

思路

我们可以使用归并排序来对链表进行排序。归并排序的基本思想是将链表分为两部分，分别对两部分进行排序，然后将两部分合并。

我们可以使用快慢指针找到链表的中点，然后将链表分为两部分。对两部分分别进行排序，然后合并两部分。

实现

function sortList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) {
    return head;
  }

  let slow: ListNode | null = head;
  let fast: ListNode | null = head;

  while (fast?.next !== null && fast?.next.next !== null) {
    slow = slow?.next ?? null;
    fast = fast.next.next;
  }

  const right = sortList(slow?.next ?? null);
  slow!.next = null;
  const left = sortList(head);

  return merge(left, right);
}

function merge(left: ListNode | null, right: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let node = dummy;

  while (left !== null && right !== null) {
    if (left.val < right.val) {
      node.next = left;
      left = left.next;
    } else {
      node.next = right;
      right = right.next;
    }

    node = node.next;
  }

  node.next = left ?? right;

  return dummy.next;
}

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是链表的长度。
• 空间复杂度：$O(\log n)$，其中 $n$ 是链表的长度。递归调用的栈空间为 $O(\log n)$。

解法二：迭代 + 节点拆分

思路

我们可以将原链表的每个节点拆分成两个节点，原节点和新节点。遍历原链表，将新节点插入到原节点的后面。再次遍历原链表，设置新节点的 random 指针。最后，将新节点从原链表中拆分出来。

实现

function copyRandomList(head: Node | null): Node | null {
  if (!head) {
    return null;
  }

  let node = head;
  while (node) {
    const newNode = new Node(node.val);
    newNode.next = node.next;
    node.next = newNode;
    node = newNode.next;
  }

  node = head;
  while (node) {
    const newNode = node.next!;
    newNode.random = node.random ? node.random.next : null;
    node = newNode.next;
  }

  const newHead = head.next;
  node = head;
  while (node) {
    const newNode = node.next!;
    node.next = newNode.next;
    node = newNode.next;
    newNode.next = node ? node.next : null;
  }

  return newHead;
};

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是链表的长度。
• 空间复杂度：$O(N)$，其中 $N$ 是链表的长度。哈希表中存储了 $N$ 个节点的映射关系。