var getIntersectionNode = function(headA, headB) {
let p1 = headA, p2 = headB
if(!p1 || !p2) return null
while(p1 !== p2){ // 如果是不相交的链表,最后都是NULL,也可以顺利退出。
p1 = p1 === null ? headB : p1.next
p2 = p2 === null ? headA : p2.next
}
return p1
};
var kthToLast = function(head, k) {
let p = head
while(k--){
p = p.next
}
let p2 = head
// 当p走完尾节点(即为null),p2停留在倒数第K个节点上
while(p && p2){
p = p.next
p2 = p2.next
}
return p2.val
};
LC 237 删除链表中的节点
删除p的下个节点:一般操作是p.next = p.next.next
var deleteNode = function(node) {
// 等于先将它下个节点复制为自己,再删除下个节点
node.val = node.next.val // 让待删除节点等于它下个节点的值
node.next = node.next.next // 再让他指向下下个节点
};
LC 83 删除排序链表中的重复元素
此题由于保证了删完每个元素都出现一次,所以头结点即使重复也不会被完全删除,所以不需要虚拟头结点
var deleteDuplicates = function(head) {
if(!head || !head.next) return head
let p = head
while(p && p.next){
if(p.val === p.next.val){
p.next = p.next.next // 删除掉p.next节点
}else{
p = p.next // 如果不重复则移到下一个节点
}
}
return head
};
LC 82 删除排序链表中的重复元素2
这题与83题不同的就是需要删除全部的重复元素,所以头结点可能会发生改变,则可以引入dummy
var deleteDuplicates = function(head) {
const dummy = new ListNode(-1, head)
let p = dummy
// p指向的是没有重复的节点,查看的是p.next和p.next.next是否重复,如果重复则删掉p.next
while(p && p.next && p.next.next){
const val = p.next.val
if(p.next.next.val === val){
// 开删
while(p.next && p.next.val === val){
p.next = p.next.next
}
}else{
p = p.next
}
}
return dummy.next
};
LC 19 删除链表的倒数第 N 个结点
基于上面的思路,可以扩展到删除倒数第N个节点
var removeNthFromEnd = function(head, n) {
const dummy = new ListNode(null, head)
let p = head
while(n--){
p = p.next
}
let p2 = head, prev = dummy // 需要使用一个prev指针指向需要删除节点的前一个节点
while(p){
p = p.next
prev = p2
p2 = p2.next
}
prev.next = p2.next
return dummy.next
};
进一步优化,可以省掉prev节点,直接让p2指向dummy节点,这样p2最后就会停留在倒数第N个节点的前一个节点
var removeNthFromEnd = function(head, n) {
const dummy = new ListNode(null, head)
let p = head
while(n--){
p = p.next
}
let p2 = dummy
while(p){
p = p.next
p2 = p2.next
}
p2.next = p2.next.next // 直接指向自己的后一个节点即可
return dummy.next
};
LC 876 链表的中间结点
快慢指针思路,经典技巧
- 首先,快慢指针都同时指向头结点
- 当节点总数是奇数时,fast走到最后一个节点,slow指向的是中间节点
- 当节点总数是偶数时,fast走到NULL,slow指向的是中间两个节点的靠后节点
var middleNode = function(head) {
let fast = head, slow = head
while(fast && fast.next){ // 注意这里是节点和节点next,都需要
slow = slow.next
fast = fast.next
if(fast){
fast = fast.next
}
}
return slow
};
LC 234 回文链表
这道题的注意点就是,需要让慢指针停留在左半段终点。按照上面👆🏻之前记录的,如果slow和fast同时出发,则偶数情况下slow指针停留在后半段的第一个点。所以这里的技巧则是让fast提前一步,从head.next出发。
var isPalindrome = function(head) {
if(!head || !head.next) return true
// fast起点比slow多一,这样可以保证不论奇偶数,slow走到的都是左半段回文串的起点,fast走到的是右半段回文串的终点
let fast = head.next, slow = head
while(fast && fast.next){
fast = fast.next.next
slow = slow.next
}
// 先翻转右半部分
let r = reverse(slow.next) // 反转链表模板
let l = head
// 再两边同时走
while(l && r){
if(l.val !== r.val) return false
l = l.next
r = r.next
}
return true
};
var hasCycle = function(head) {
let slow = head, fast = head
while(fast && fast.next){
slow = slow.next
fast = fast.next.next
if(slow === fast) return true // 同样的模板题,只需要在循环内判断他们是否最终相遇
}
return false
};
LC 142 环形链表2
假设 直线为距离a,环口->相遇点为距离b,从相遇点->环口为距离c。b+c即为环长。
可以得到 快指针走的距离: a + b + k * (b + c) ,慢指针走的距离:a + b
由于快指针比慢指针相对速度快1倍,所以也等价于快指针走的距离是2倍慢指针的距离,即 2*(a + b)
即:2 * (a + b) = a + b + k * (b + c)
=> 2 * a + 2 * b = a + b + (b + c) + (k - 1) * (b + c) // 拆出一个b+c
=> a - c = (k - 1) * (b + c)
=> a = c + (k - 1) * 环长
所以,在相遇之后把slow指针移到head处,等于是让b刚好走 (k-1) * 环长 - c的距离,那么最后相遇点一定是环口。
var detectCycle = function(head) {
let slow = head, fast = head
while(fast && fast.next){
slow = slow.next
fast = fast.next.next
if(fast === slow){
slow = head // 慢指针重新再走,最终一定会在环口相遇
while(fast !== slow){
slow = slow.next
fast = fast.next
}
return slow
}
}
return null
};
143 重排链表
经典技巧组合题
var reorderList = function(head) {
const middle = findMiddle(head) // 快慢指针模板
let p1 = head
let p2 = reverseList(middle) // 反转链表模板
while(p2.next){
const next = p1.next
const next2 = p2.next
// 1->2 null<-3<-4
p1.next = p2 // 1->4
p2.next = next // 4->2
p1 = next // p1 = 2
p2 = next2 // p2 = 3
}
};
var reverseBetween = function(head, left, right) {
const dummy = new ListNode(null, head)
let p0 = dummy
for(let i = 0; i < left - 1; i++){
p0 = p0.next
}
let prev = null
p = p0.next // start
for(let i = 0; i < right - left + 1; i++){ // 翻转这段一共有 right - left + 1 个元素
const next = p.next
p.next = prev
prev = p
p = next
}
// 此时,prev就是翻转后的头结点(实例1中的节点4),p指向的就是right的下一个(实例1中的5)
// p0.next当前指向的是实例1中的节点2,
p0.next.next = p
p0.next = prev
return dummy.next
};
var reverseKGroup = function(head, k) {
// 先求出列表总长度
let n = 0
let p = head
while(p){
p = p.next
n += 1
}
// 下面的代码和 翻转部分链表一致
const dummy = new ListNode(null, head)
let p0 = dummy
p = p0.next
while(n >= k){ // 增加一个while循环,判断下面长度是否满足k个
n -= k
let prev = null
for(let i = 0; i < k; i++){
const nxt = p.next
p.next = prev
prev = p
p = nxt
}
const nxt = p0.next // 这里需要存一下p0.next,即是当前翻转完毕的最后一个节点(作为下一段待翻转段的p0节点)
p0.next.next = p
p0.next = prev
p0 = nxt // 最后更新p0
}
return dummy.next
};
// 相当于是翻转2个一组的链表
var swapPairs = function(head) {
let n = 0
let p = head
while(p){
n++
p = p.next
}
const dummy = new ListNode(null, head)
let p0 = dummy
p = p0.next
while(n >= 2){
n -= 2
let prev = null
for(let i = 0; i < 2; i++){
const nxt = p.next
p.next = prev
prev = p
p = nxt
}
const next = p0.next
p0.next.next = p
p0.next = prev
p0 = next
}
return dummy.next
};
var addTwoNumbers = function(l1, l2) {
const reverse = (head) => {
let prev = null
let p = head
while(p){
const next = p.next
p.next = prev
prev = p
p = next
}
return prev
}
let p1 = reverse(l1)
let p2 = reverse(l2)
let t = 0
let dummy = new ListNode(-1)
p = dummy
while(p1 || p2){
const p1Val = p1 ? p1.val : 0
const p2Val = p2 ? p2.val : 0
const sum = p1Val + p2Val + t
p.next = new ListNode(sum % 10)
t = sum / 10 | 0
p = p.next
p1 = p1 ? p1.next : null
p2 = p2 ? p2.next : null
}
if(t){
p.next = new ListNode(t)
p = p.next
t = 0
}
return reverse(dummy.next)
};
var rotateRight = function(head, k) {
if(!head || !head.next) return head
let n = 0
let p = head
while(p){
p = p.next
n++
}
const dummy = new ListNode(-1, head)
p = head
k = k % n
while(k--){
p = p.next
}
let p2 = head
while(p && p.next){
p2 = p2.next
p = p.next
}
// p在最后一个节点,p2此时在倒数第k+1个的位置上
p.next = head
dummy.next = p2.next
p2.next = null // 先连再断
return dummy.next
};