自己做报名网站建设旅游网站目的

当前位置： 首页 > news >正文

自己做报名网站,建设旅游网站目的,网站开发简历的项目经验,江苏省建设工程招标网24. 两两交换链表中的节点 题目链接#xff1a; 24. 两两交换链表中的节点 文档讲解#xff1a;代码随想录 状态#xff1a;没做出来#xff0c;没有正确更新头节点#xff0c;因为head和cur共享引用#xff0c;会随着cur的移动#xff0c;丢失之前存放的节点 错误代码 24. 两两交换链表中的节点 文档讲解代码随想录 状态没做出来没有正确更新头节点因为head和cur共享引用会随着cur的移动丢失之前存放的节点 错误代码 public ListNode swapPairs(ListNode head) {ListNode cur head;ListNode next;ListNode temp;while (cur ! null cur.next ! null) {next cur.next;temp next.next;next.next cur;cur.next temp;cur temp;}return head;}思路前面博客中总结过啥时候需要使用虚拟头结点这边需要返回head节点所以使用dummy节点然后cur从dummy出发。 public ListNode swapPairs(ListNode head) {// 创建一个虚拟节点dummy.next 指向 headListNode dummy new ListNode();dummy.next head;// cur 用于遍历链表初始化为 dummy 节点ListNode cur dummy;ListNode first; // 用于指向要交换的第一个节点ListNode second; // 用于指向要交换的第二个节点ListNode temp; // 用于暂存第二个节点的下一个节点// 当 cur 后面至少有两个节点时继续交换while (cur.next ! null cur.next.next ! null) {first cur.next; // 定位要交换的第一个节点second cur.next.next; // 定位要交换的第二个节点temp second.next; // 暂存第二个节点的下一个节点// 进行节点交换first.next temp; // 第一个节点的 next 指向第二个节点的 nextsecond.next first; // 第二个节点的 next 指向第一个节点cur.next second; // 当前节点的 next 指向第二个节点// cur 移动到已交换的两个节点之后的位置cur first;}// 返回新的头节点return dummy.next; } 19.删除链表的倒数第N个节点 题目链接 19.删除链表的倒数第N个节点 文档讲解代码随想录 状态so easy 思路 看到“返回链表的头结点”使用虚拟头结点dummy删除倒数第N个节点就需要先找到它然后对它进行操作。 方式1遍历一遍得到len然后倒数第n个节点就是len-n1个节点。 方式2利用栈先所有节点入栈然后出栈n个节点此时栈顶元素就是倒数第N1个节点让它的next节点指向下下个节点即可。 方式3利用双指针中的快慢指针让fast指针先走n步然后和slow指针同时移动当fast指针指向null时slow指针指向倒数第N1个节点让它的next节点指向下下个节点即可。 双指针题解 public ListNode removeNthFromEnd(ListNode head, int n) {// 创建一个虚拟节点dummy.next 指向 headListNode dummy new ListNode();dummy.next head;// 初始化快指针和慢指针都指向虚拟节点ListNode fast dummy;ListNode slow dummy;// 让快指针先移动 n 步while (n– 0 fast.next ! null) {fast fast.next;}// 同时移动快指针和慢指针直到快指针到达链表末尾while (fast.next ! null) {fast fast.next;slow slow.next;}// 慢指针的下一个节点就是要删除的节点slow.next slow.next.next;// 返回新的头节点return dummy.next;}面试题 02.07. 链表相交 题目链接 面试题 02.07. 链表相交(同160.链表相交) 文档讲解代码随想录 状态没做出来一个bug卡了很久。 错误代码 // 在每一轮循环中指针先移动到下一个节点然后才判断是否为null并进行重定向。这会导致在指针都为null时直接重定向而没有机会检查pointerA pointerB是否成立导致死循环。public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pointerA headA;ListNode pointerB headB;while (pointerA ! pointerB) {pointerA pointerA.next;pointerB pointerB.next;if (pointerA null) {pointerA headB;}if (pointerB null) {pointerB headA;}}return pointerA;}思路1可以使用HashMapheadA中的节点都存在map中遍历headB时检查是否在map中存在该节点。如果存在则这个节点就是交点 思路2双指针。pA遍历headApB遍历headB当pA遍历到尾部时重定向到headB当pB遍历到尾部时重定向到headA如果存在相同节点则会两个指针在同一个节点相遇。 双指针题解 /*** 法二:双指针* 指针 pA和pB 指向同一个节点或者都为空时返回它们指向的节点或者 null* p这边指向相同节点的是8不是5也不是1哦,前面的5和1只是值相等,地址不等* 4 1 8 4 5#5 0 1 8 4 5* 5 0 1 8 4 5#4 1 8 4 5*/public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 初始化两个指针分别指向两个链表的头节点ListNode pA headA;ListNode pB headB;// 遍历两个链表直到找到交点或者遍历结束while (pA ! pB) {// 如果当前指针不为空则移动到下一个节点否则重定向到另一个链表的头部pA (pA ! null) ? pA.next : headB;pB (pB ! null) ? pB.next : headA;}// 返回交点的节点如果没有交点则返回nullreturn pA;}142.环形链表II 题目链接 142.环形链表II 文档讲解代码随想录 状态还行 思路1遍历head节点用HashSet检查是否有出现过的同一节点如果没有就将遍历到的节点存入HashSet否则返回的节点就是环的入口节点 思路2数学方法快慢指针 快慢指针题解 // 使用快慢指针法找到单链表中的环的入口点public ListNode detectCycle(ListNode head) {// 初始化快慢指针初始位置为链表头部ListNode fast head, slow head;// 防止空链表或者不存在环的情况while (true) {// 如果快指针或者快指针的下一个节点为null说明不存在环返回nullif (fast null || fast.next null) {return null;}// 快指针每次移动两步慢指针每次移动一步fast fast.next.next;slow slow.next;// 如果快慢指针相遇说明存在环跳出循环if (fast slow) {break;}}// 将快指针重新指向链表头部慢指针不变fast head;/当快慢指针再次相遇时即为环的入口点这是因为在快慢指针相遇时慢指针走过的距离从链表头到环入口点的距离与快指针走过的距离之间存在一定的关系。假设链表头到环入口点的距离为A快慢指针相遇点距离环入口点的距离为B环的周长为C。当快慢指针相遇时快指针已经在环内绕了n圈所以慢指针走的距离是A B而快指针走的距离是ABnC。由于快指针是慢指针的两倍速度因此有关系快指针走过的距离是慢指针的两倍。可以得到以下方程ABnC2(AB从而可以推导出A n-1CC-B这意味着将快指针重新指向链表头部然后慢指针和快指针以相同的速度前进它们将在环的入口点相遇。这是因为慢指针走了n—1圈的环再走C—B的距离就到达了环的入口点,而根据公式,同样的速度快指针从链表头步出发,此时刚好也走了距离A,此时两个指针在入口点相遇/while (slow ! fast) {slow slow.next;fast fast.next;}// 返回环的入口点return fast;}