链表算法题
链表题常见解法
- 创建一个新链表。
let newHead = new ListNode()
需要使用到记录【前一个节点】这种概念时，要用到 newHead 这种虚拟头节点
- 记录 被循环的节点 的next。
const next = currentNode.next
链表考什么？就是哨兵节点+虚拟节点+链表指针的移动
- 链表节点的交换，插入等等，每记录一个节点，下一步就是对其进行替换，如
const next = p.next; p.next = xxx
双指针
- 要删除一个节点，需要知道这个节点的前一个节点，判断条件得是
p.next。p.next = p.next.next代表p还指向旧p，抛弃了next，用于要连续判断后继节点时p = p.next.next代表跳过了p，还跳过了next，指向了新p
头部可能插值的问题都需要一个头空结点
2、反转链表（ LeetCode 206 ）
一个一个插入到newRoot节点后面，先记录下一个节点，再 currentNode.next = root.next
var reverseList = function(head) {
let newHead = new ListNode(-1)
while(head) {
const next = head.next
head.next = newHead.next
newHead.next = head
head = next
}
return newHead.next
};
// 极简
var reverseList = function(head) {
let [prev, current] = [null, head]
while(current) {
[current.next, prev, current] = [prev, current, current.next]
}
return prev
}
// 递归
// 假设列表的其余部分已经被反转，现在我们应该如何反转当前节点？
// 1.如果为null则当前就是头节点，返回
// 2.先反转后续的节点
// 3.再反转当前节点
var reverseList = function(head) {
if (head === null || head.next === null) { return head; }
const newHead = reverseList(head.next); // 从最后一个结点开始轮，此处返回最后一个结点
head.next.next = head; // 倒数第二个 的下一个结点 的next 指向当前结点
head.next = null; // 当前结点 也就是 倒数第二个结点 next为null
// 每一层 递归都记录了当前结点，所以直接把next置为null也没关系
// 外层会继续将next 置为前一个数
return newHead;
}3、相交链表（ LeetCode 160 ）
循环条件是pA !== pB
// 相交链表
var getIntersectionNode = function(headA, headB) {
let p1 = headA,p2 = headB
while(p1 !== p2) {
p1 = p1 === null ? headB : p1.next
p2 = p2 === null ? headA : p2.next
}
return p1
};
// 两个指针走的路程必然等长，不会无限循环，在 AB同为null时已经跳出循环了4、合并两个有序链表 （ LeetCode 21 ）
// 迭代
var mergeTwoLists = function(l1, l2) {
const preHead = new ListNode(-1);
let prev = preHead;
while (l1 && l2) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 === null ? l2 : l1;
return preHead.next;
};// 递归
var mergeTwoLists = function(l1, l2) {
if (l1 === null) {
return l2;
} else if (l2 === null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};5、分隔链表 （ LeetCode 86 ）
var partition = function(head, x) {
let small = new ListNode(0);
const smallHead = small;
let large = new ListNode(0);
const largeHead = large;
while (head !== null) {
if (head.val < x) {
small.next = head;
small = small.next;
} else {
large.next = head;
large = large.next;
}
head = head.next;
}
large.next = null;
small.next = largeHead.next;
return smallHead.next;
};
// 空间复杂度0
var partition = function(head, x) {
let p = root = new ListNode(-1, head)
while(p.next && p.next.val < x) {
p = p.next
}
let p2 = p.next
if(!p2) return root.next
while(p2.next) {
if(p2.next.val < x) {
const temp = p2.next
p2.next = p2.next.next
temp.next = p.next
p.next = temp
p = p.next
} else {
p2 = p2.next
}
}
return root.next
};6、环形链表 II （ LeetCode 142 ）
// 我想的是在节点上做标记，显然用set更好，记住这思路
var detectCycle = function(head) {
const visited = new Set();
while (head !== null) {
if (visited.has(head)) {
return head;
}
visited.add(head);
head = head.next;
}
return null;
};// 要理解 快慢指针 找链的环结构入口,要理解两个重要结论,
// 1.慢指针 走过的的长度 等于 环的长度
// 2.慢指针 从头走到环入口的长度 等于 慢指针 从相遇点走完剩余环的长度
// 假设 快指针 一次走 2个节点,慢指针 一次走 1个节点
// 假设 头到环入口长度 a, 环长度 b.
// 第 1 次相遇时, 快指针总路程 f,慢指针总路程 s,此时可得到两个等式
// (注意是第1次相遇,如果继续跑,第1次相遇后,s每跑1圈,f会跑2圈,会再次在这相遇,算法只需要考虑第1次相遇就行)
// f(快指针路程) = 2s(慢指针走的路程) (快指针是慢指针两倍速)
// f(快指针路程) = s(慢指针走的路程) + b(环的长度)
// 得到 s = b (慢指针走的路程 就是 环的长度b)
// 可理解为,第一次相遇的时候,s还刚进 第1圈,f已经多走了1圈环,所以 s=b
// 所以得到 重要结论 (1) 慢指针路程 s = b 环的节点数
// 接下来要思考,直觉上来说,为什么再次从头开始走一个 慢指针2
// 同时从第一次相遇处 走 慢指针1,两个慢指针必然会在 环入口处相遇?
// 换句话说 为什么 慢指针1 走完 剩余环的长度(y),会等于 从头到入环 的长度?
// 此时,我们整理下, 头到环入口a, 环入口到相遇处(x), 环长度b
// 很显然 环的长度(b) = x(入口到相遇处) + y(相遇处到环入口)
// 同时由结论(1) 环的长度(b) = s(慢指针路径) = a(头到环入口) + x(入口到相遇处)
// x(入口到相遇处) + y(相遇处到环入口) = a(头到环入口) + x(入口到相遇处)
// 语言解释就是, 头到相遇处, 相遇处再到环入口,是等长的,重合部分就是 入口到相遇处
// 路径上来说,都减去重合部分(入口到相遇处x),剩余部分路径相等
// 如果 假设两个慢指针,都不走重合部分,一个从头开始走,一个跳过重合部分从相遇处开始走
// 相同速度,走过相同路径时,便会相遇在入口
var detectCycle = function (head) {
let fast = slow = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (fast === slow) {
let p = head
while(p !== slow) {
p = p.next
slow = slow.next
}
return p
}
}
return null
};7、反转链表 II （ LeetCode 92 ）
// 要点，拆分子列，标记 左前与右 结点，左与右后 结点
var reverseBetween = function(head, left, right) {
const pointH = new ListNode(-1,head) // 这类头部可能插值的问题都需要一个头空结点
let pointL = pointH // 指向子链表left前一个结点
for (let i = 0; i < left - 1; i++) {// 右移到left位置-1
pointL = pointL.next
}
let pointR = pointL // 指向子链表right结点
for (let i = 0; i < right - left + 1; i++) { // 右移差值+1个位置
pointR = pointR.next
}
// 切出子链表，记录子链表头部 left，尾部 right的后一个结点
let plr = pointL.next // 子链表的头部 left结点
let prr = pointR.next // 子链表尾部 right的后一个结点
// 切断
pointL.next = null
pointR.next = null
pointL.next = reverseLinkedList(plr) // 左前结点拼上反转后的子链
plr.next = prr // plr结点反转后已经是子链的right尾结点
return pointH.next
};
var reverseLinkedList = function(head) {
let root = null
while(head) {
const nextNode = head.next
head.next = root
root = head
head = nextNode
}
return root
}更优的解法,头插法
把下一个标记出来，再插入头部之后。
var reverseBetween = function(head, left, right) {
// 设置 dummyNode 是这一类问题的一般做法
const dummy_node = new ListNode(-1);
dummy_node.next = head;
let pre = dummy_node;
for (let i = 0; i < left - 1; ++i) {
pre = pre.next;
}
let cur = pre.next;
for (let i = 0; i < right - left; ++i) {
const next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy_node.next;
};8、复制带随机指针的链表（ LeetCode 138 ）
先创建一批具有val的新节点，制作新旧node的映射，再循环原链表，通过原node，拿到新node，并赋值next，random等。
var copyRandomList = function (head) {
if(head == null) { return null }
let map = new Map() // map记录结点
let cur = head;
while(cur){
map.set(cur,new Node(cur.val)) // 先创建一个个新节点，并储存
cur = cur.next;
}
cur = head;
while(cur){
const curNode = map.get(cur)
curNode.next = cur.next? map.get(cur.next):null // 根据旧节点，从hashMap拿到新节点
curNode.random = map.get(cur.random)
cur = cur.next;
}
return map.get(head);
}9、移除链表元素（ LeetCode 203 ）
var removeElements = function(head, val) {
if(head === null) return null
let tmpHead = new ListNode(-1) // 可能删除头节点的都得先设置伪头部
tmpHead.next = head
let cur = tmpHead
while(cur.next) {
if(cur.next.val === val) { // 删除了下一个就不用跳
cur.next = cur.next.next || null
} else {
cur = cur.next
}
}
return tmpHead.next
};10、删除有序数组中的重复项（ LeetCode 26 ）
慢指针 左侧为已经去重的数组，右侧为待去重的数组
循环快指针，如果 当前节点 与上一节点不同，
代表当前节点是新节点(非重复节点)，放入慢指针位置，慢指针+1，快指针+1
如果 当前节点 与上一节点相同，代表为重复节点，不做操作，快指针+1并再次判断。
var removeDuplicates = function(nums) {
const length = nums.length
if(length === 0) return 0
let f = s = 1
while(f < length) {
if(nums[f] !== nums[f-1]) {
nums[s] = nums[f]
s++
}
f++
}
return s
};11、移动零（ LeetCode 283 ）
将数组内所有0移动到数组末尾
慢指针 左侧为已经去0的数组，右侧为待去0的数组
循环快指针，如果 当前节点 不是0，
放入慢指针位置，慢指针+1，快指针+1，保持慢指针左侧去0
如果 当前节点 是0，不做操作，快指针+1并再次判断。
var moveZeroes = function(nums) {
const length = nums.length
let f = s = 0
while(f < length) {
if(nums[f] !== 0) {
nums[s] = nums[f]
s++
}
f++
}
while(s < length) {
nums[s] = 0
s++
}
return nums
};12、合并两个有序数组（ LeetCode 88 ）
nums1 的长度为 m + n
nums1 的元素个数为 m
nums2 的元素个数为 n
leetcode
为避免消除了nums1中的待比对元素，采取从后向前 比对 和 放置的方式
cur指针右侧为 已比对元素， 左侧为待比对元素
循环i2，当i2小于0，代表nums2中的所有元素已放入nums1中，代表合并结束
i1 i2 >= 0,代表其数组还有未对比的数。
如果 i1>=0，并且i1数更大，cur处放i1，i1–，左移进行下一轮判断
如果 i2 数更大或相等，cur处放i2，保持从左往右从小到大。
（注意,为什么要加上 i1>=0 这个条件，因为
如果 i1<0,代表nums1数组所有数已排完,剩下cur左侧位置全放剩下的nums2就行，无需比较i1，i2大小）
var merge = function (nums1, m, nums2, n) {
let cur = m + n - 1
let p1 = m - 1
let p2 = n - 1
while (p2 >= 0) {
nums1[cur] = p1 >= 0 && nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--]
cur--
}
return nums1
};13、K 个一组翻转链表（ LeetCode 25 ）
需要使用到记录【前一个节点】这种概念时，要用到 newHead 这种虚拟头节点
标记好 要翻转的链表 头(start) 尾(fast)，断开处的 头的前一(slow) 尾的后一(next) 四个节点
并将 要翻转的链表 与主体断开，准备进行反转。
然后 反转链表，反转后，(start)成为了 新尾，(reverse)返回的是 新头
最后 旧头的前一(slow) 拼接 (reverse)返回值， 新尾(start) 拼接 尾的后一(next)
(fast)(slow)均指向 新尾(start)，继续进行后续翻转。
直到fast无结果
var reverseKGroup = function (head, k) {
const newHead = new ListNode(-1, head)
let slow = fast = newHead
while (fast.next) {
for (let i = 0; i < k && fast; i++) {
fast = fast.next
}
if (!fast) break
const next = fast.next
fast.next = null
const start = slow.next
slow.next = null
slow.next = reverse(start)
start.next = next
slow = start
fast = start
}
return newHead.next
};
var reverse = function (head) {
const newHead = new ListNode(-1)
while (head) {
const next = newHead.next
newHead.next = head
head = head.next
newHead.next.next = next
}
return newHead.next
}14、加一（ LeetCode 66 ）
用一个数组模拟一个非负整数，如 [1,2,3] 代表 123，
给这个数+1，并返回，如 [1,2,4]
先将末位数 +1，然后循环从后往前判断进位
var plusOne = function (digits) {
const index = digits.length - 1
digits[index] = digits[index] + 1
for (let i = index; i >= 0; i--) {
if (digits[i] !== 10) { break; }
digits[i] = 0
if (i - 1 >= 0) {
digits[i - 1] = digits[i - 1] + 1
} else {
digits.unshift(1)
}
}
return digits
};
