双指针技巧|链表篇刷题合集
剑指 Offer 18. 删除链表的节点
单指针:
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var deleteNode = function(head, val) {
let prehead=new ListNode(-1);
prehead.next=head;
let p=prehead;
while(prehead &&prehead.next){//要考虑当prehead为最后一个结点时
if(prehead.next.val===val){//当prehead为最后一个结点时，prehead.next为null，没有val，会报错
prehead.next=prehead.next.next;
}
prehead=prehead.next;
}
return p.next;
};
踩了个坑，注意while的判断条件为倒数第二个结点！！
剑指 Offer 24. 反转链表
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let pre=null;//反转后的尾结点指向null
let curnode=head;
while(curnode){
let next = curnode.next;//保存下一节点
curnode.next=pre;//链表反转
pre=curnode;//更新pre和curnode，即移动指针
curnode=next;
}
return pre;
};
剑指 Offer 25. 合并两个排序的链表
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： 0 \le n \le 10000≤n≤1000，-1000 \le 节点值 \le 1000−1000≤节点值≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}
思路：
双指针：这道题既然两个链表已经是排好序的，都是从小到大的顺序，那我们要将其组合，可以使用归并排序的思想：每次比较两个头部，从中取出最小的元素，然后依次往后。这样两个链表依次往后，我们肯定需要两个指针同方向访问才能实现。
具体过程：
- step 1：判断空链表的情况，只要有一个链表为空，那答案必定就是另一个链表了，就算另一个链表也为空。
- step 2：新建一个空的表头后面连接两个链表排序后的节点，两个指针分别指向两链表头。
- step 3：遍历两个链表都不为空的情况，取较小值添加在新的链表后面，每次只把被添加的链表的指针后移。
- step 4：遍历到最后肯定有一个链表还有剩余的节点，它们的值将大于前面所有的，直接连在新的链表后面即可。
function ListNode(x){
this.val = x;
this.next = null;
}
function Merge(pHead1, pHead2)
{
// write code here
if (!pHead1) return pHead2;
if (!pHead2) return pHead1;
let cur=new ListNode(0);
let head=cur;
while(pHead1 && pHead2){
if (pHead1.val <=pHead2.val){
cur.next = pHead1;
pHead1=pHead1.next;
}
else {
cur.next = pHead2;
pHead2=pHead2.next;
}
cur=cur.next;
}
if (pHead1) cur.next = pHead1;
else cur.next = pHead2;
return head.next;
}
module.exports = {
Merge : Merge
};
剑指 Offer 22. 链表中倒数第k个节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let p1=head;
for(let i=0;i<k;i++){//p1走k步
p1=p1.next;
}
let p2=head;
while(p1){//p1、p2再走n-k步
p1=p1.next;
p2=p2.next;
}
return p2;//指向第n-k个结点，即为倒数第k个结点(走n-k步)
};剑指 Offer II 021. 删除链表的倒数第 n 个结点
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let prenode=new ListNode(0);// 虚拟头节点
prenode.next=head;
let x=Finend(prenode,n+1)// 删除倒数第 n 个，要先找倒数第 n + 1 个节点
x.next=x.next.next;
return prenode.next;
};
function Finend(head, k){
let p1=head;
for(let i=0;i<k;i++){//p1走k步
p1=p1.next;
}
let p2=head;
while(p1){//p1、p2再走n-k步
p1=p1.next;
p2=p2.next;
}
return p2;//指向第n-k个结点，即为倒数第k个结点(走n-k步)
}
快慢指针技巧
876. 链表的中间结点
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var middleNode = function(head) {
let fast=head;
let slow=head;
while(fast&&fast.next)//要加上判断fast.next,使快指针在终点停止遍历
{
fast=fast.next.next;
slow=slow.next;
}
return slow;
};
141. 环形链表
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let fast=slow=head;
while(fast&&fast.next){//踩坑点，fast为最后一个结点的话fast.next为null了，null无next，故要判断fast.next
fast=fast.next.next;
slow=slow.next;
if(slow==fast) return true;
}
return false;
};
踩坑点:注意while的判断终止条件为fast是最后一个结点(while(fast)会报错)
剑指 Offer II 027. 回文链表
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
let arr=[];
while(head!==null){//将链表存入数组
arr.push(head.val);
head=head.next;
}
for(let i=0,j=arr.length - 1;i < j;i++,j--){//从后往前和前往后判断
if (arr[i] !== arr[j]) {
return false;
}
}
return true;
};
剑指 Offer II 022. 链表中环的入口节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {//方法1
let set=new Set();
while(head){
if(set.has(head)) return head;//用哈希表set来实现，判断再次出现的结点
set.add(head);
head=head.next;
}
return null;
};
//方法2，快慢指针
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
let fast=slow=head;
while(fast&&fast.next){//踩坑点，fast为最后一个结点的话fast.next为null了，null无next，故要判断fast.next
fast=fast.next.next;
slow=slow.next;
if(slow==fast) break;
}
slow=head;
if(!fast || !fast.next) return null;
while(fast !== slow){
fast=fast.next;
slow=slow.next;
}
return slow;
};
160. 相交链表
很简单的方法就是用哈希表，下面是快慢指针:
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let p1=headA,p2=headB;
while(p1!==p2){//核心是把链表合并
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if(p1==null) p1=headB;
else p1=p1.next;
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if(p2==null) p2=headA;
else p2=p2.next;
}
return p1;
};
核心是把A,B链表连接起来，让p1和p2能够同时到达相交节点。
https://mp.weixin.qq.com/s/dVqXEMKZ6_tuB7J-leLmtg
阅读剩余
版权声明：
作者：chun
链接：https://chun53.top/1213.html
文章版权归作者所有，未经允许请勿转载。
THE END