我要评论⚡刷题计划day4继续，可以点个免费的赞哦~
下一期将会开启哈希表刷题专题，往期可看专栏，关注不迷路，
您的支持是我的最大动力🌹~
目录
题目一：19. 删除链表的倒数第 n 个结点
leetcode:19. 删除链表的倒数第 n 个结点
(https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/)
法一：计算链表长度
常规思路：先遍历得到链表长度l，然后再次遍历到 l-n+1个结点，便是我们需要删除的结点；
这里我们还是使用虚拟头结点统一，于是从虚拟结点开始遍历l-n+1个结点，它的下一个结点便是我们要删除的结点，这样我们只需修改一次指针，就可完成删除操作。
如图辅助理解：
ac代码
class solution {
public listnode removenthfromend(listnode head, int n) {
listnode dummyhead = new listnode();
dummyhead.next=head;
listnode cur = dummyhead;
int length = getlength(head);
for (int i=1;i<length-n+1;i++){
cur = cur.next;
}
if(cur.next!=null){//避免空指针
cur.next = cur.next.next;//删除操作
}
return dummyhead.next;
}
public int getlength(listnode head){
int length = 0;
while(head != null){
length++;
head=head.next;
}
return length;
}
}
法二：双指针
主要思路：
要删除倒数第n个，我们可以使用双指针，这样不用去求长度；
保持一个相差n的区间，fast在前,slow在后。这样等fast走到链表末尾，slow对应的就是我们要删除的结点；
因为链表删除我们需要通过前一个结点，所以将相差区间设为n+1，可以结合图理解：
ac代码
class solution {
public listnode removenthfromend(listnode head, int n) {
listnode dummyhead = new listnode();
dummyhead.next=head;
listnode fast = dummyhead;
listnode slow = dummyhead;
// 只要快慢指针相差 n 个结点即可
for (int i=1;i<=n+1;i++){
fast = fast.next;
}
while (fast!=null){
fast = fast.next;
slow = slow.next;
}
if(slow.next!=null){
slow.next = slow.next.next;
}
return dummyhead.next;
}
}题目二：面试题 02.07. 链表相交
leetcode：面试题 02.07. 链表相交
(https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/)
简单来说，就是求两个链表交点节点的指针。 这里要注意，交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
看如下两个链表，目前cura指向链表a的头结点，curb指向链表b的头结点：
我们求出两个链表的长度，并求出两个链表长度的差值，然后让cura移动到，和curb 末尾对齐的位置，如图
此时我们就可以比较cura和curb是否相同，如果不相同，同时向后移动cura和curb，如果遇到cura == curb，则找到交点。
否则循环退出返回空指针。
ac代码
法一：双指针
public class solution {
public listnode getintersectionnode(listnode heada, listnode headb) {
// 初始化两个链表的当前节点
listnode cur1 = heada;
listnode cur2 = headb;
// 初始化两个链表的长度
int len1 = 0;
int len2 = 0;
// 求cur1长度
while (cur1 != null) {
len1++;
cur1 = cur1.next;
}
// 求cur2长度
while (cur2 != null) {
len2++;
cur2 = cur2.next;
}
// 重新初始化两个链表的当前节点
cur1 = heada;
cur2 = headb;
// 如果第一个链表比第二个短，交换两个链表的头节点和长度
if (len1 < len2) {
//1. swap (len1, len2);
int temp = len1;
len1 = len2;
len2 = temp;
//2. swap (cur1, cur2);
listnode temnode = cur1;
cur1 = cur2;
cur2 = temnode;
}
// 计算长度的差值
int gap = len1 - len2;
// 移动较长链表的当前节点，使cur1与cur2的末尾位置对齐，看图
while (gap-- > 0) {
cur1 = cur1.next;
}
// 同时遍历两个链表，遇到相同则直接返回
while (cur1 != null) {
if (cur1 == cur2) {
return cur1; // 返回相交的节点
}
cur1 = cur1.next;
cur2 = cur2.next;
}
// 如果两个链表没有相交，返回null
return null;
}
}法二：合并链表实现同步移动
主要思路：
-
同步移动指针：
-
使用一个
while循环，只要p1和p2没有相遇，就继续移动指针。 -
对于
p1，如果它到达了链表a的末尾（即p1为null），则将它移动到链表b的头部，重新开始遍历。 -
对于
p2，如果它到达了链表b的末尾（即p2为null），则将它移动到链表a的头部，重新开始遍历。
-
-
相遇即相交：
-
当两个指针
p1和p2相遇时，它们指向的就是链表相交的节点。因为两个指针最终都会遍历完两个链表，如果链表有相交点，它们最终会在相交点相遇。
-
-
返回结果：
-
一旦
p1和p2相遇，即它们指向同一个节点，就返回这个节点。
-
public class solution {
public listnode getintersectionnode(listnode heada, listnode headb) {
// p1 指向 a 链表头结点，p2 指向 b 链表头结点
listnode 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;
}
}题目三：142. 环形链表 ii
leetcode：142. 环形链表 ii
(https://leetcode.cn/problems/linked-list-cycle-ii/description/)
法一：快慢指针法
判断链表是否有环，我们一般可以使用快慢指针法
此题还是有一定难度，考察了对链表环的判断，已经需要进行数学运算，下文会进行详细解释。
对于此题大致分为两大步：
1.判断链表是否有环
2.如果有环，如何找到环的入口
1.判断链表是否有环
分别定义fast,slow指针，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
2.如果有环，如何找到环的入口
这步已经可以判断链表是否有环了，接下来是寻找环的入口，需要用到一点数学运算。
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：
那么当相遇时：
slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数a。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 slow指针走过的节点数 * 2 = fast指针走过的节点数，所以可以列出方程：
(x + y) * 2 = x + y + n (y + z)
因为我们要找环形入口，即需要找x，将x单独放出来化简：
x = n (y + z) - y
但是我们看一下这个式子呢，也发现不了什么，我们是想通过右边的参数来求x，但发现目前右侧也没啥特殊形式，还有个-y。于是我们可以提一个(y+z)出来，
x = (n - 1) (y + z) + z(此处n>=1，前面有解释)
此时就明了了。
2.1 n==1
当 n为1的时候，公式就化解为 x = z，
这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
2.2 n>1
那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。
其实这种情况和n为1的时候效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
代码如下：
public class solution {
public listnode detectcycle(listnode head) {
listnode fast = head;
listnode slow = head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
//相遇,有环
if(fast==slow){
listnode index1 = fast;
listnode index2 = head;
// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
while (index1 != index2){
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}
法二：哈希表
这个思路就简单很多，时间复杂度：o(n)，空间复杂度：o(n)；
但第一种双指针的解法也需要掌握，时间复杂度：o(n)，空间复杂度：o(1)。
关于哈希表我们下期也会做相应的专题刷题。
主要思路：遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。
代码：
详细见注解
public class solution {
public listnode detectcycle(listnode head) {
// 初始化指针pos指向头结点
listnode pos = head;
// 使用hashset来存储已经访问过的节点
set<listnode> visited = new hashset<listnode>();
// 遍历链表
while (pos != null) {
// 如果当前节点已经被访问过，说明存在环，返回当前节点
if (visited.contains(pos)) {
return pos;
} else {
// 否则，将当前节点添加到visited集合中
visited.add(pos);
}
// 移动到下一个节点
pos = pos.next;
}
// 如果遍历完整个链表都没有发现环，返回null
return null;
}
}
发表评论