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;
}
复杂度分析
- 时间复杂度:,其中 是链表的长度。
- 空间复杂度:,其中 是链表的长度。递归调用的栈空间为 。
解法二:迭代 + 节点拆分
思路
我们可以将原链表的每个节点拆分成两个节点,原节点和新节点。遍历原链表,将新节点插入到原节点的后面。再次遍历原链表,设置新节点的 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;
};
复杂度分析
- 时间复杂度:,其中 是链表的长度。
- 空间复杂度:,其中 是链表的长度。哈希表中存储了 个节点的映射关系。