目录
21.合并两个有序链表
题目描述
ts
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]代码
ts
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
if (list1 === null && list2 === null) return null;
const head = new ListNode();
let curr = head;
while(list1 && list2) {
if (list1.val < list2.val) {
curr.next = new ListNode(list1.val, null);
list1 = list1.next;
} else {
curr.next = new ListNode(list2.val, null);
list2 = list2.next;
}
curr = curr.next;
}
curr.next = list1 === null ? list2 : list1;
return head.next;
};82.删除排序链表中的重复元素 II
题目描述
ts
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]代码
ts
function deleteDuplicates(head: ListNode | null): ListNode | null {
if (head === null) return head;
let result: ListNode = new ListNode();
let curr: ListNode = result;
while(head) {
if (head.next && head.next.val === head.val) {
while(head.next && head.val === head.next.val) {
head = head.next;
}
} else {
curr.next = new ListNode(head.val);
curr = curr.next;
}
head = head.next;
}
return result.next;
};83.删除排序链表中的重复元素
题目描述
ts
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]代码
ts
function deleteDuplicates(head: ListNode | null): ListNode | null {
if (head === null) return null;
let curr: ListNode = head;
while(curr.next) {
if (curr.val !== curr.next.val) {
curr = curr.next;
} else {
curr.next = curr.next.next;
}
}
return head;
};86.分隔链表
题目描述
ts
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]代码
ts
function partition(head: ListNode | null, x: number): ListNode | null {
let result = new ListNode();
let curr = result;
let head2 = head;
while(head) {
if (head.val < x) {
curr.next = new ListNode(head.val);
curr = curr.next;
}
head = head.next;
}
while(head2) {
if (head2.val >= x) {
curr.next = new ListNode(head2.val);
curr = curr.next;
}
head2 = head2.next;
}
return result.next;
};92.反转链表 II
题目描述
ts
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]代码
ts
function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
let result = new ListNode(-1, head);
let pre: ListNode | null = result;
for (let i = 1; i < left && pre; i++) pre = pre.next;
if (!pre) return result.next;
const start = pre.next;
let curr: ListNode | null = null;
for (let i = 0; i < right - left ; i++) {
if (!start || !start.next) break;
curr = start.next;
start.next = curr.next;
curr.next = pre.next;
pre.next = curr;
}
return result.next;
};138.随机链表的复制
太难了，不想做。
141.环形链表
题目描述
ts
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。代码
ts
function hasCycle(head: ListNode | null): boolean {
if (head == null || head.next == null) return false;
let fast: ListNode | null = head.next
while (fast && fast.next && head) {
if (fast == head) {
return true;
}
head = head.next;
fast = fast.next.next
}
return false;
};142.环形链表 II
题目描述
ts
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。。代码
ts
function detectCycle(head: ListNode | null): ListNode | null {
let nodeArr: ListNode[] = [];
while(head) {
if (nodeArr.includes(head)) return head;
nodeArr.push(head);
head = head.next;
}
return null;
};143.重排链表
有点挑战性：寻找链表中点 + 链表逆序 + 合并链表
题目描述
ts
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]
示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]代码
ts
function reorderList(head: ListNode | null): void {
if (head == null || head.next == null) return;
// 找到中间节点
let slow: ListNode | null = head;
let fast: ListNode | null = head;
while(fast && fast.next && slow) {
slow = slow.next;
fast = fast.next.next;
}
// 反转链表
let reverse: ListNode | null = null;
while(slow) {
const next = slow.next;
slow.next = reverse;
reverse = slow;
slow = next;
}
// 合并链表
slow = head;
fast = reverse;
head = new ListNode();
let curr = head;
while(slow && fast) {
const slowNext = slow.next;
curr.next = slow;
curr.next.next = fast;
slow = slowNext;
fast = fast.next;
curr = curr.next.next;
}
curr.next = null;
head = head.next;
};148.排序链表
太难了，不想做。
206.反转链表
题目描述
ts
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]代码
ts
function reverseList(head: ListNode | null): ListNode | null {
let result: ListNode | null = null;
let curr = head;
while(curr) {
const next = curr.next;
curr.next = result;
result = curr;
curr = next;
}
return result;
};