MsBlog

【力扣】插入

题目：给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。题目保证从 i 位到 j 位足以容纳 M，例如： M

2021-04-29

1031

【力扣】环路检测

本文介绍了如何检测链表中的环，并找到环的起始节点。文章提供了两种方法：第一种是使用集合（Set）存储遍历过的节点，当遇到重复节点时即为环的入口；第二种方法利用快慢指针技巧，通过让两个指针以不同速度移动来检测环的存在。当快慢指针相遇时，再引入一个从头开始的新指针与慢指针同步移动，直到两者再次相遇，此时相遇点即为环的起点。这种方法不需要额外空间，更加高效。代码示例展示了这两种解决方案的具体实现。

【力扣】链表相交

本文介绍了如何判断两个单向链表是否相交，并找到它们的交点。题目要求基于节点引用而不是值来判断相交。文章提供了两种解法：第一种是使用集合（Set）存储第一个链表的所有节点，然后遍历第二个链表检查是否存在相同的节点；第二种方法是采用双指针技术，通过调整两个指针的移动路径，使得当一个指针到达链表末尾时转向另一个链表头部继续遍历，最终两指针会在相交节点相遇或同时为null。这两种方法都能有效地解决问题，且后者满足O(n)时间复杂度和O(1)空间复杂度的要求。

【力扣】回文链表

该文章介绍了两种方法来判断一个链表是否为回文结构。第一种方法是将链表中的所有元素复制到数组中，然后使用双指针技术从两端向中间移动并比较元素值，时间复杂度为O(n)，空间复杂度为O(n)。第二种方法则是先找到链表的中点，反转后半部分链表，之后再逐个比较前半部分与反转后的后半部分节点值，以确定整个链表是否构成回文。这种方法在保持O(n)时间复杂度的同时，仅需O(1)的空间复杂度。通过这两种不同的方式，可以有效解决检查链表是否为回文的问题。

【力扣】链表求和

该题目要求实现一个函数，用于计算两个以链表形式表示的整数之和，并将结果同样以链表形式返回。给定的链表中每个节点包含一个数位，且这些数位是反向存放的（即个位在链表头部）。解题思路模仿了基本的加法运算规则：逐位相加并处理进位。具体实现时，通过遍历两个输入链表，同时维护一个额外变量`carray`来追踪当前是否有进位需要处理。每一步都创建一个新的链表节点来存储当前位的结果值（即两数相应位及进位之和对10取余），并将这个新节点添加到结果链表中。最后返回构建好的结果链表，去除最开始为了方便操作而创建的虚拟头节点。对于更进一步的问题，如果数字是正向存放，则需要先反转链表再进行上述相同的操作。

【力扣】分割链表

该题目要求编写一个程序，以给定值x为基准分割链表，确保所有小于x的节点位于大于或等于x的节点之前。解题思路是遍历原始链表，将小于x的节点添加到一个小链表中，大于等于x的节点则加入另一个大链表。最后，将这两个链表连接起来形成新的有序链表。具体实现时，通过创建两个虚拟头节点来分别管理小链表和大链表，在完成对原链表的遍历后，将大链表接在小链表之后，并返回合并后的链表头部。这样就完成了链表的重新排序。

【力扣】删除中间节点

本文介绍了如何在只能访问目标节点的情况下，从单向链表中删除一个非首尾节点的方法。具体实现是将待删除节点的值替换为其下一个节点的值，然后跳过下一个节点，从而达到删除效果。示例中，对于链表a->b->c->d->e->f，若要删除节点c，则首先将c的值替换为d的值，再令c指向e，最终链表变为a->b->d->e->f。提供的Java代码实现了这一逻辑，并包含了一个建议性的垃圾回收调用（通常不推荐直接使用）。这种方法简单有效，能够快速完成指定节点的删除操作。

【力扣】返回倒数第k个节点

本文介绍了两种解决LeetCode中“寻找单向链表倒数第k个节点”问题的方法。第一种方法通过两次遍历实现：首先遍历整个链表以计算节点总数，然后再次遍历至指定位置找到目标节点。第二种方法采用双指针技术仅需一次遍历完成任务，其中一个指针先于另一个移动k步，随后两者同步前进直至前者到达链尾，此时后者所指向的即为所求节点。这种方法提高了效率，减少了遍历次数。