体育网站建设需求,开发外包公司有哪些?哪个比较好,网站包装推广之网络营销案例,建站代理⚡刷题计划day4继续#xff0c;可以点个免费的赞哦~
下一期将会开启哈希表刷题专题#xff0c;往期可看专栏#xff0c;关注不迷路#xff0c;
您的支持是我的最大动力#x1f339;~ 目录
⚡刷题计划day4继续#xff0c;可以点个免费的赞哦~
下一期将会开启哈希表刷题…⚡刷题计划day4继续可以点个免费的赞哦~
下一期将会开启哈希表刷题专题往期可看专栏关注不迷路
您的支持是我的最大动力~ 目录
⚡刷题计划day4继续可以点个免费的赞哦~
下一期将会开启哈希表刷题专题往期可看专栏关注不迷路
您的支持是我的最大动力~
题目一19. 删除链表的倒数第 N 个结点
法一计算链表长度
法二双指针
题目二面试题 02.07. 链表相交
法一双指针
法二合并链表实现同步移动
题目三142. 环形链表 II
法一快慢指针法
1.判断链表是否有环
2.如果有环如何找到环的入口
2.1 n1
2.2 n1
法二哈希表 题目一19. 删除链表的倒数第 N 个结点
leetcode:19. 删除链表的倒数第 N 个结点
(https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/) 法一计算链表长度
常规思路先遍历得到链表长度L然后再次遍历到 L-n1个结点便是我们需要删除的结点
这里我们还是使用虚拟头结点统一于是从虚拟结点开始遍历L-n1个结点它的下一个结点便是我们要删除的结点这样我们只需修改一次指针就可完成删除操作。
如图辅助理解 AC代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyHead new ListNode();dummyHead.nexthead;ListNode cur dummyHead;int length getLength(head);for (int i1;ilength-n1;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;headhead.next;}return length;}
} 法二双指针
主要思路
要删除倒数第n个我们可以使用双指针这样不用去求长度
保持一个相差n的区间fast在前,slow在后。这样等fast走到链表末尾slow对应的就是我们要删除的结点
因为链表删除我们需要通过前一个结点所以将相差区间设为n1可以结合图理解 AC代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyHead new ListNode();dummyHead.nexthead;ListNode fast dummyHead;ListNode slow dummyHead;
// 只要快慢指针相差 n 个结点即可for (int i1;in1;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;}
// 如果两个链表没有相交返回nullreturn 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
leetcode142. 环形链表 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指针 yz为 一圈内节点的个数A。 加深理解注 1.fast指针为什么 n (y z) 因为fast比slow快fast进入圈后至少需要一圈后追反超slow由此也可知道n1后续解题会用。 2.为什么slow就不用比如k(yz) 因为slow进入圈后在一圈内一定会被fast追上 3.那为什么slow一圈内就一定会被fast追上呢 可以这样通俗理解首先fast会比slow快1如果slow走一圈fast就会走两圈那一定会追上。 因为fast指针是一步走两个节点slow指针一步走一个节点 所以 slow指针走过的节点数 * 2 fast指针走过的节点数所以可以列出方程
(x y) * 2 x y n (y z)
因为我们要找环形入口即需要找x将x单独放出来化简
x n (y z) - y
但是我们看一下这个式子呢也发现不了什么我们是想通过右边的参数来求x但发现目前右侧也没啥特殊形式还有个-y。于是我们可以提一个(yz)出来
x (n - 1) (y z) z(此处n1前面有解释)
此时就明了了。 2.1 n1
当 n为1的时候公式就化解为 x z
这就意味着从头结点出发一个指针从相遇节点也出发一个指针这两个指针每次只走一个节点 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处定义一个指针index1在头结点处定一个指针index2。
让index1和index2同时移动每次移动一个节点 那么他们相遇的地方就是 环形入口的节点。
2.2 n1
那么 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(fastslow){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来存储已经访问过的节点SetListNode visited new HashSetListNode();
// 遍历链表while (pos ! null) {// 如果当前节点已经被访问过说明存在环返回当前节点if (visited.contains(pos)) {return pos;} else {// 否则将当前节点添加到visited集合中visited.add(pos);}// 移动到下一个节点pos pos.next;}
// 如果遍历完整个链表都没有发现环返回nullreturn null;}
}
