# 链表
单在真题归纳解读环节 能做的题目已经有很多
- 链表的处理：合并、删除等（删除操作画个记号，重点中的重点！）
- 链表的反转及其衍生题目
- 链表成环问题及其衍生题目
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
# 链表的循环
function listFor(l1) {
if (!l1) {
return
}
let cur = l1 // 链表要循环 先要有一个游标 来定位当前的结点位置
while (cur) {
console.log(cur.val)
cur = cur.next // 游标的移动
}
}
listFor(l1)
TIP
游标的移动 cur = cur.next
# 链表的重复删除
83. 删除排序链表中的重复元素 (opens new window)
真题描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 输入: 1->1->2 输出: 1->2
function deleteList(l1) {
let cur = l1
while (cur !== null && cur.next !== null) {
// cur.next=0
if (cur.val === cur.next.val) {
cur.next = cur.next.next // 删除下一个结点
} else {
cur = cur.next // 游标结点移动
}
}
return l1
}
TIP
删除下一个节点 cur.next = cur.next.next 删除了下一个结点 不要在移动游标
# 链表的合并
21. 合并两个有序链表 (opens new window)
真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
TIP
处理链表的本质，是处理链表结点之间的指针关系。
// 链表的基本数据结构
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
const head = new ListNode()
let cur = head
while (list1 && list2) {
if (list1.val <= list2.val) {
cur.next = list1
list1 = list1.next
} else {
cur.next = list2
list2 = list2.next
}
cur = cur.next
}
cur.next = list1 === null ? list2 : list1
return head.next
}
TIP
链表的添加节点 cur.next = next
# 删除问题的延伸
82. 删除排序链表中的重复元素 II (opens new window)
真题描述：给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中 没有重复出现的数字。
输入: 1->2->3->3->4->4->5 输出: 1->2->5
function deleteMutNumber(list) {
if (list === null || list.next === null) {
return
}
const dummy = new ListNode()
dummy.next = list
let cur = dummy
// 链表的循环退出结点的判断 怎么证明结点有没有值 上一个结点的next 为null
while (cur.next && cur.next.next) {
if (cur.next.val === cur.next.next.val) {
cur.next = cur.next.next
let val = cur.next.val
// 反复地排查后面的元素是否存在多次重复该值的情况
while (cur.next && cur.next.val === val) {
// 若有，则删除 链表的删除 怎么删除一个结点 这个结点的上一个结点直接指向这个结点的下一个结点
cur.next = cur.next.next
}
} else {
cur = cur.next // 链表的循环 游标怎么下一步 直接时当前游标重新赋值为一下个结点
}
}
return dummy.next
}
TIP
定义 dummy 节点: const dummy = new ListNode();dummy.next = head
# 快慢指针——删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点 (opens new window)
真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个结点后，链表变为 1->2->3->5.
var removeNthFromEnd = function(head, n) {
const dum = new ListNode()
dum.next = head
let fast = dum
let slow = dum
for (let i = 0; i < n; i++) {
fast = fast.next
}
while (fast.next !== null) {
slow = slow.next
fast = fast.next
}
slow.next = slow.next.next
return dum.next
}
# 多指针法——链表的反转
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
function (head){
let per = null
let cur = head
while(cur!==null){
const next = cur.next
cur.next = per
per = cur
cur = next
}
return per
}
TIP
开始进行翻转一定要知道他的前驱结点和当前的结点
# 局部反转一个链表
真题描述：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
var reverseBetween = function(head, left, right) {
// 定义pre、cur，用leftHead来承接整个区间的前驱结点
let pre, cur, leftHead
const dumany = new ListNode()
dumany.next = head
// 游标
let p = dumany
for (let i = 0; i < left - 1; i++) {
p = p.next
}
leftHead = p
let start = p.next
per = start
cur = start.next
for (let i = 0; i < right - left; i++) {
const next = cur.next
cur.next = per
per = cur
cur = next
}
leftHead.next = per
// 将区间内反转后的最后一个结点 next 指向 cur
start.next = cur
return dumany.next
}
TIP
局部反转 先找到开始反转节点的前驱节点
TIP
链表做题前画图
# 环形链表基本问题——如何判断链表是否成环
真题描述：给定一个链表，判断链表中是否有环。 输入：[3,2,0,4] pos=1 输出：true
// 立flag
var hasCycle = function(head) {
while (head) {
if (head.flag) {
return true
} else {
head.flag = true
head = head.next
}
}
return false
}
// 双指针
var hasCycle = function(head) {
if (!head) return false
let slow = head
let fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) {
return true
}
}
return false
}
# 问题
什么时候要头结点？