我报名参加金石方案1期挑战——瓜分10万奖池,这是我的第1篇文章,点击查看活动概况”
- 分类刷算法题
- 之前陆陆续续刷了一些,可是感觉都没有真正掌握起来吧,做的题乱七八糟,所以这次决定好好收拾一下好好过一遍
- 今日要刷的是链表
一、 链表的兼并
- 剑指 Offer 25. 兼并两个排序的链表 – 力扣(LeetCode)
- 主要运用的便是’牵线搭桥’的思路,比较两个,那个比较小就给那个串起来
- 难度:简略
- 思路:
- 初始化dummy伪结点,cur指向dummy结点
-
进入while循环:当l1为空或许l2为空时跳出循环
- 当l1.val<l2.val时,cur后继结点指向l1,l1向前走一步
- 当l1.val<l2.val时,cur后继结点指向l2,l2向前走一步
- cur向前走一步
- 兼并剩余的部分
var mergeTwoLists = function(l1, l2) {
let dummy = new ListNode();
let cur = dummy;
//两个都节点都存在时,就一向穿梭引线
while(l1 && l2) {
//当l1的值比较小的时分,cur的next指向l1,反之指向l2
if(l1.val< l2.val) {
cur.next = l1
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
//串起一个结点后,‘针’也要向前走一步
cur = cur.next;
}
//最终剩下的就给它直接一整串串起来
cur.next = l1 === null? l2:l1;
return dummy.next
};
二、链表的删去
- 83. 删去排序链表中的重复元素 – 力扣(LeetCode)
- 这个很常见也很基础
- 难度: 简略
- 思路:
- cur指向head
- 进入while循环:当cur指向结点为空或cur的后继结点为空时跳出循环
- 假如cur指向结点值等于其后继结点的值,则让他的后继结点指向其后继结点的后继结点
- 不然cur向前走一步
var deleteDuplicates = function(head) {
let cur = head;
while(cur != null && cur.next!= null) {
if(cur.val == cur.next.val) {
cur.next = cur.next.next
}else{
cur = cur.next
}
}
return head
};
- 82. 删去排序链表中的重复元素 II – 力扣(LeetCode)
- 难度:中等
- 这道题便是上一道题的衍生了,这道题需求把重复的悉数删去,那么就或许出现头结点也要删去遇到这种情况咱们就要加他加上dummy伪头结点,才能够next指向真实头结点对他进行删去
- 思路:
- 初始化dummy结点:让他的后继节点指向head,一起cur指向dummy
-
进入while循环:cur的后继节点或cur的后继节点的后继节点为空时跳出循环
- 当cur的后继节点值等于其后继节点的后继节点值时,遍历其后继节点,对该值节点进行删去
- 不然的话cur向前走一步
var deleteDuplicates = function(head) {
//dummy伪头结点
let dummy = new ListNode();
dummy.next = head;
let cur = dummy;
while(cur.next && cur.next.next) {
if(cur.next.val == cur.next.next.val) {
let val = cur.next.val
while(cur.next && cur.next.val == val) {
cur.next = cur.next.next;
}
}else{
cur = cur.next;
}
}
return dummy.next
};
- 剑指 Offer 18. 删去链表的节点 – 力扣(LeetCode)
- 难度:简略
- 如上一道题所述,看到删去节点有或许删去第一个节点咱们或许就要设置伪头结点啦;
- 一起这道题说的是删去一个节点,也便是说假如头结点是需求删去的节点话,咱们能够采用另一种办法,遇到删去节点为头结点时直接回来head.next就行
- 以上两种思路跟上述题都差不多就不赘述啦
//设置伪头结点
var deleteNode = function(head, val) {
let dummy = new ListNode();
dummy.next = head;
let cur = dummy;
while(cur && cur.next) {
if(cur.next.val == val) {
cur.next = cur.next.next;
return dummy.next
}else{
cur = cur.next;
}
}
};
//遇到头结点需求删去,直接回来head.next
var deleteNode = function(head, val) {
if(head.val == val) return head.next;
let cur = head;
while(cur && cur.next) {
if(cur.next.val == val) {
cur.next = cur.next.next;
return head;
}else{
cur = cur.next;
}
}
};
- 剑指 Offer II 021. 删去链表的倒数第 n 个结点 – 力扣(LeetCode)
- 难度: 中等
- 这道题咱们采纳新的思路-快慢指针
- 遇到触及相对杂乱的链表操作,比方回转、指定方位的删去等等常常需求触及到重复遍历,解决这类题,咱们用到的是双指针中的“快慢指针”
- 快慢指针指的是两个一前一后的指针,两个指针往同一个方向走,只是一个快一个慢
- 触及链表操作、尤其是触及结点删去的标题,我都主张我们写代码的时分直接把
dummy
给用起来,建立好的编程习惯,这个在后面也不会再赘述啦 - 还有一道很类似的题,做完这道题也能够试一试喔:剑指 Offer 22. 链表中倒数第k个节点 – 力扣(LeetCode)
- 思路:
- 设置伪头结点
- 初始化快指针fast, 慢指针low 都指向dummy
- 先让快指针走K步(意图:当快指针走到最终的结点时,慢结点刚好指向倒数第K个结点的前继结点)
- 让快慢指针同频向前走直到fast走到最终的结点
- 删去慢指针的后继节点
var removeNthFromEnd = function(head, n) {
let dummy = new ListNode();
dummy.next = head;
let fast = dummy;
let slow = dummy;
while(n!=0) {
fast = fast.next;
n--
}
while(fast.next) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next
};
做完上述的题还能够试试以下的题哦
203. 移除链表元素 – 力扣(LeetCode): 这个题跟上述剑指offer18的题很像
三、链表回转
- 剑指 Offer II 024. 回转链表 – 力扣(LeetCode)
- 难度: 简略
- 上述标题咱们用到了双指针法的快慢指针,那咱们这道题用一下多指针法
- pre,cur,next顺次指向接连结点
- pre为cur的前继结点,用于回转链表
- cur为当前结点,通过cur遍历
- next指向cur的后继节点,避免回转后丢掉后继链表
var reverseList = function(head) {
let pre = null;
let cur = head;
while(cur) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre
};
- 92. 回转链表 II – 力扣(LeetCode)
- 难度:中等
- 这道题跟上一道题很像,不相同的是上一道题是悉数回转,这道题属于部分回转
- 采用先回转再拼接,所以记住要把left的前一个节点和right的后一个节点记录下来
- 思路:
- 初始化伪头结点dummy
- 初始化leftNode,rightNode,通过for循环让其别离指向left的前继结点和right节点
- 堵截
- 部分回转(直接采用上一道题的代码)
- 拼接
- 这道题直接做或许会容易乱,画个图就好啦~
var reverseBetween = function(head, left, right) {
let dummy = new ListNode();
dummy.next = head;
let leftNode = dummy;
let rightNode = dummy;
//走到left的前继结点
for(let i =0 ;i<left-1; i++) {
leftNode = leftNode.next;
}
//走到right结点
for(let i=0; i<right; i++) {
rightNode = rightNode.next;
}
//记录下list1和list2
let list1 = leftNode.next;
let list2 = rightNode.next;
//堵截
leftNode.next = null;
rightNode.next = null;
//回转中心链表
let list3 = reverseList(list1);
//拼接
leftNode.next = list3;
list1.next = list2;
//回来
return dummy.next
};
var reverseList = function(head) {
let pre = null;
let cur = head;
while(cur) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre
};
四、环形链表
- 141. 环形链表 – 力扣(LeetCode)
- 难度: 简略
- 遇到环形的还能够多加一个判断:假如只有两个结点的话,是无法构成环形的
- 这道题的办法太多啦而且都是很常见的办法
- 能够运用哈希表,哈希表存储已经通过的结点,假如通过的节点相同的就阐明环形了
- 也能够运用上面说过的双指针里边的快慢指针:假如链表是环形的,那么快指针必定会追上慢指针
- 也能够运用最简略的符号办法:我通过就把它的flag变为true,只有我通过的节点flag为true,那么必定成环了
var hasCycle = function(head) {
//运用快慢指针
//假如只有两个节点也构不成环形链表
if(head == null || head.next == null || head.next.next == null) return false
let n1 = head;
let nn = head.next;
while(n1 != nn){
//下一个节点能够为空阐明不环形
if(nn.next == null || nn.next.next == null) {
return false;
}
//一个每次走一步一个每次走两步,构成快慢
n1 = n1.next;
nn = nn.next.next;
}
return true
};
var hasCycle = function(head) {
//运用flag
//假如只有两个节点也构不成环形链表
if(head == null || head.next == null || head.next.next == null) return false
while(head) {
if(head.flag) {
return true
}else{
head.flag = true;
head = head.next;
}
}
return false
};
- 142. 环形链表 II – 力扣(LeetCode)
- 难度:中等
- 这道题跟上面基本相同啦,改一下回来值就好啦
var detectCycle = function(head) {
if(head == null || head.next == null || head.next.next == null) return null
while(head) {
if(head.flag) {
return head
}else{
head.flag = true;
head = head.next;
}
}
return null
};
五、链表的相交
- 160. 相交链表 – 力扣(LeetCode)
- 难度: 简略
- 这个题的思路便是假如我相交的话,那么两个指针别离在两个链表走一遍,那么必定会有相交的结点
- 若两链表 有 公共尾部 (即 c > 0c>0 ) :指针 A , B 一起指向第一个公共节点node
- 若两链表 无 公共尾部 (即 c = 0c=0 ) :指针 A , B 一起指向 null
var getIntersectionNode = function(headA, headB) {
//假如有一个链表为空的话那么必定不会相交
if(headA === null || headB === null) return null
let pA = headA;
let pB = headB;
//这儿没有相交是不会死循环哦,因为会一起指向null,也是持平;所以退出循环不必定是没有相交
while(pA != pB) {
//假如pA指向的为空,则切换到headB ,不然就指向其后继节点
pA = pA === null? headB: pA.next;
//假如pB指向的为空,则切换到headA ,不然就指向其后继节点
pB = pB === null? headA: pB.next;
}
return pA
};
六、其他链表题
- 876. 链表的中心结点 – 力扣(LeetCode)
- 难度:简略
- 当快指针走到最终的时分,慢指针刚好在中心结点
var middleNode = function(head) {
//运用快慢指针
let fast = head;
let slow = head;
while(fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
}
return slow
};
以上代码是自己做题的总结,或许不行完美哈哈哈,主张仍是多看看LeetCode的题解喔
还能够看看其他分类刷题集哦
- 分类刷算法题(二)栈和队列 | 前端er – ()
- 分类刷算法题(三)数组操作 | 前端er – ()
- 分类刷算法题(四) 二分查找 | 前端er – ()
- 分类刷算法题 (五) 二叉树 | 前端er – ()