leetcode刷题(javaScript)——链表相关场景题总结
链表中的元素在内存中不是顺序存储的,而是通过next指针联系在一起的。常见的链表有单向链表、双向链表、环形链表等
在 JavaScript 刷题中涉及链表的算法有很多,常见的包括:
1. 遍历链表:从头到尾遍历链表,处理每个节点的值或指针。
2. 反转链表:将链表的指针方向反转,使链表的尾部变为头部。
3. 合并两个有序链表:将两个有序链表合并成一个有序链表。
4. 删除链表中的指定节点:删除链表中特定值或位置的节点。
5. 检测链表中是否有环:判断链表中是否存在环形结构。
对于新手刷题链表,一些需要注意的方法和建议包括:
1. 熟悉链表的基本操作:了解链表的基本结构和操作,包括节点的定义、指针操作等。
2. 注意边界情况:在处理链表时,要考虑边界情况,如空链表、只有一个节点的链表等。
3. 使用递归:递归是解决链表问题的常见方法,可以简化问题的复杂度。
4. 双指针技巧:在解决链表问题时,双指针技巧经常会派上用场,例如快慢指针用于检测环。
5. 利用辅助数据结构:有时候可以借助辅助数据结构如哈希表来解决链表问题。
206. 反转链表
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
思路:新创建一个链表,链表头指针pre,新的链表用pre指向,最后返回这个头指针。
1——》2——》3——》4——》5——》null
可以转换为
null《——1《——2《——3《——4《——5
pre初始是空对象pre = null
难点来了
怎么实现null《——1 让1的next指向null呢?
如果1的next改变指向,那么2以及之后的数据将丢失,所以需要提前将1的next暂存给一个变量;
然后这个时候可以改变1的next指向为pre了。
那原始链表还需要遍历呀,这个时候将暂存的next赋给current。同时pre也从null后移指向1.所以第二次遍历结束
2——》3——》4——》5——》null
^
current指向2
null《——1
^
pre指向
第三次遍历结束
3——》4——》5——》null
^
current指向3
null《——1《——2
^
pre指向
这道题可能当时做会了过段时间就忘了,所以要牢记改变指向的时候数据连接会丢失,需要考虑丢掉还是要保留,如果要保留数据,一定在改变指向前处理。
/** * 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 prev = null; let current = head; while (current !== null) { let nextNode = current.next; current.next = prev; prev = current; current = nextNode; } return prev; };
使用迭代的方式遍历链表,将每个节点的指针方向反转。使用 prev 指针来保存已经反转部分的链表,current 指针来遍历原始链表。在每一步中,我们将 current.next 指向 prev,然后更新 prev 和 current 指针继续向后移动,直到遍历完整个链表。
最后,返回反转后的链表的头节点,即 prev 指针所指向的节点,这个节点就是原始链表的尾节点,也就是反转后链表的头节点。
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */ var mergeTwoLists = function (list1, list2) { if (!list1) return list2; if (!list2) return list1; let head = new ListNode(0, null); let cur = head; while (list1 && list2) { let val; if (list1.val为了正确地创建 ListNode 的实例,应该使用 new ListNode(val, null)而不是ListNode(val,null)这是因为创建的是节点的实例而不是单纯的调用函数。这里的ListNode是构造函数。
怎么区分普通函数和构造函数?
- 看大小写:一般构造函数函数名的首字母会大写,普通函数是小写。
- 函数中的this指向不同:普通函数的this在严格模式下指向undefined,非严格模式指向window对象。构造函数的this指向它创建的对象实例。
构造函数的执行流程
- 立即创建一个新的对象
- 将新建的对象设置给函数中的this,在构造函数中可使用this来引用新建的对象
- 逐行执行函数中的代码
- 将新建的对象作为返回值返回
237. 删除链表中的节点——改变元素指向
有一个单链表的 head,我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。
链表的所有值都是 唯一的,并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意,删除节点并不是指从内存中删除它。这里的意思是:
- 给定节点的值不应该存在于链表中。
- 链表中的节点数应该减少 1。
- node 前面的所有值顺序相同。
- node 后面的所有值顺序相同。
思路:不删除当前node节点,又没有上一个元素的信息,不能更改上一个元素指向node.next。从node出发,让node变成node.next,跳过node.next这个节点。我变成了他,同时,让他消失。。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} node * @return {void} Do not return anything, modify node in-place instead. */ var deleteNode = function(node) { node.val = node.next.val; node.next = node.next.next; };
node.val = node.next.val让node替换成node.next元素
node.next = node.next.next 干掉node.next
node替代node.next结束
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
/** * 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 deleteDuplicates = function (head) { if (!head) return head; let cur = head; while (cur.next) { if (cur.val === cur.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; };
思路:比较简单的链表删除,题目已经保证是排序好的链表,只用考虑相邻元素重复的情况。当前元素和下一个元素重复的话,将当前元素的next指向,下下一个元素。跳过重复的。
如果没有重复,指针往后移动一个。注意需要返回排序后的数组,所以头指针的指向不能变,最后返回head指针。过程用cur指针替代head进行向后移动。
141. 环形链表——快慢指针
如果链表中存在环,快指针和慢指针最终会在环中相遇;如果链表中不存在环,快指针会先到达链表尾部。
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
使用快慢指针的技巧来检测链表中是否存在环。具体来说,定义了两个指针 f 和 s,初始时都指向链表的头部。然后,使用一个循环来遍历链表,其中快指针 f 每次移动两步,慢指针 s 每次移动一步。如果链表中存在环,快指针 f 会在某个时刻追上慢指针 s,此时就可以判断链表中存在环,返回 true;如果快指针 f 到达链表尾部(即 f 或 f.next 为 null),则说明链表中不存在环,返回 false。
这种算法的时间复杂度为 O(n),其中 n 是链表的长度。
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {boolean} */ var hasCycle = function (head) { let f = head, s = head; while (f != null && f.next != null) { s = s.next; f = f.next.next; if (s == f) return true; } return false; };
使用双等号 == 运算符来比较两个对象并不会直接比较它们的内容,而是比较它们的引用。
s==f则快指针和慢指针指向了同一个对象
160. 相交链表
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
这道题,如果不看题解,第一次做肯定没有思路
首先比较的不是节点的值相等,而是指向同一个节点。
其次,一般会考虑n^2时间复杂度,穷举A,对A的每项在穷举B
其实只要找到A、B的起始位,让A和B可以同步向后 移动。
例如,上图中,如果B一开始指向b2,那么比较b2和a1,不相等,均向后移动一位,比较a2和b3是否相等。不等,在往后移动,比较c1和c1是否相等,相等则返回A或B当前指向的节点
要找出两个单链表相交的起始节点,可以使用双指针法。具体步骤如下:
- 分别遍历两个链表,计算它们的长度。
- 计算两个链表的长度差,然后让较长的链表的指针先移动长度差个节点,使得两个链表剩余的长度相等。
- 同时遍历两个链表,比较节点是否相同,找到相交的起始节点。
/** * 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 curA = headA; let curB = headB; let lengthA = getLength(curA); let lengthB = getLength(curB); if (lengthB > lengthA) { let step = lengthB - lengthA; while (step--) { curB = curB.next; } } else if (lengthB
注意在计算链表长度时不要破坏传入的head指针指向,要创建新的变量指向head指针。
拿到lengthA和lengthB后可以判断哪个更长,移动长的链表的cur指针。
A和B的cur指针同步移动时无论判断while(curA)还是while(curB)都可以,因为剩余要比较的链表长度相等呀,比较次数也相等
当A和B的cur指向一样,同理,返回curA或curB都行,结束判断
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]
示例 2:
输入:head = [], val = 1 输出:[]
示例 3:
输入:head = [7,7,7,7], val = 7 输出:[]
思路:这道题诈看很简单,用指针遍历,当前元素和val相等时,用下一个元素替换当前元素。这种方法在最后一个元素时会失效,因为无法杀死最后一个元素了,最后一个元素和它前一个连接无法断开。
那如果在头节点之前新增一个节点呢,用cur的next节点参与比较。当遇到最后一个元素时,其实是示例中的5.next ===6,让5.next=null即可,杀死了最后一个元素6
/** * 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} val * @return {ListNode} */ var removeElements = function (head, val) { let newNode = new ListNode(0, head); let cur = newNode; while (cur) { if (cur.next && cur.next.val === val) { cur.next = cur.next.next; } else { cur = cur.next; } } return newNode.next; };
这里用newNode指向新创建的链表,最后返回的是newNode.next,因为头加入了一个无用的节点。
用next节点参与比较,当前元素改变它的next指向即可
876. 链表的中间结点
给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
方法一:首先遍历一遍单链表,记录链表的长度len,计算中间节点的位置。 用空间换时间:
/** * 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 cur = head; let setp = Math.floor(getLength(head) / 2); while (setp--) { cur = cur.next; } return cur; }; function getLength(head) { let cur = head; let length = 0; while (cur) { length++; cur = cur.next; } return length; }
当我用这种方法写完,时间复杂度n+n/2感觉没那么简单,一看评论区,果然大神就是多,双指针,时间复杂度为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 * @return {ListNode} */ var middleNode = function (head) { let f = head; let s = head; while (f && f.next) { f = f.next.next; s = s.next; } return s; };
简直了,只要思想简单,代码就简单。这里判断f.next.next最后一步是等于null所以f.next不能为null,f也不能为null。