已经有域名如何做网站,手机优化加速有什么用,中国猎头公司排行榜,seo网络推广技术目录
一#xff1a;重排链表#xff08;LeetCode.143#xff09; 二#xff1a;删除链表的节点#xff08;LCR 136. 删除链表的节点#xff09;
三#xff1a;K个一组反转链表#xff08;LeetCode.25#xff09; 有关经典算法链表的第一篇内容#xff0c;可以查看我…目录
一重排链表LeetCode.143 二删除链表的节点LCR 136. 删除链表的节点
三K个一组反转链表LeetCode.25 有关经典算法链表的第一篇内容可以查看我的上一篇内容经典算法之链表篇一
一重排链表LeetCode.143
问题描述 给定一个单链表 L 的头节点 head 单链表 L 表示为 L0 → L1 → … → Ln-1 → Ln请将其重新排列后变为 L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 示例 输入: head [1,2,3,4] 输出: [1,4,2,3] 示例2 输入: head [1,2,3,4,5] 输出: [1,5,2,4,3] 解题思路 找到链表中点使用快慢指针找到链表的中点。快指针每次移动两步慢指针每次移动一步当快指针到达链表末尾时慢指针指向链表中点。 反转后半部分链表从中点处将链表分为两部分将后半部分链表进行反转。 合并链表将前半部分链表和反转后的后半部分链表依次交替合并即可得到重新排列后的链表。 处理边界情况需要注意链表为空或只有一个节点的情况直接返回即可 图示 第一步 第二步 第三步 第四步 代码实现
class ListNode {int val;ListNode next;ListNode(int x) { val x; }
}class Solution {public void reorderList(ListNode head) {if (head null || head.next null) return;// 找到链表的中间节点ListNode slow head;ListNode fast head;while (fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;}// 反转后半部分链表ListNode pre null;ListNode cur slow.next;slow.next null; // 断开前后两部分链表while (cur ! null) {ListNode next cur.next;cur.next pre;pre cur;cur next;}// 合并两部分链表ListNode p1 head;ListNode p2 pre;while (p2 ! null) {ListNode tmp1 p1.next;ListNode tmp2 p2.next;p1.next p2;p2.next tmp1;p1 tmp1;p2 tmp2;}}
}public class Main {public static void main(String[] args) {int[] nums {1, 2, 3, 4, 5};ListNode head createList(nums);// 重排链表Solution solution new Solution();solution.reorderList(head);// 输出重排后的链表printList(head);}// 创建链表public static ListNode createList(int[] nums) {if (nums.length 0) return null;ListNode head new ListNode(nums[0]);ListNode cur head;for (int i 1; i nums.length; i) {cur.next new ListNode(nums[i]);cur cur.next;}return head;}// 输出链表public static void printList(ListNode head) {ListNode cur head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}
} 二删除链表的节点LCR 136. 删除链表的节点 问题描述 给定单向链表的头指针和一个要删除的节点的值定义一个函数删除该节点。 返回删除后的链表的头节点。 示例 输入: head [4,5,1,9], val 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点那么在调用了你的函数之后该链表应变为 4 - 1 - 9. 解题思路 判断链表是否为空若为空直接返回 nullptr。 创建一个虚拟头节点 dummy并将其指向头节点 head这样做是为了方便处理头节点的删除操作。 初始化两个指针 pre 和 cur分别指向虚拟头节点和头节点。 遍历链表查找要删除的节点 如果当前节点的值等于要删除的值 val则将前一个节点 pre 的 next 指针指向当前节点的下一个节点 cur-next即完成删除操作。 否则更新 pre 和 cur 指针继续遍历链表。 完成遍历后更新头节点 head 为虚拟头节点的下一个节点 dummy-next即删除可能存在的头节点。 释放虚拟头节点的内存避免内存泄漏。 返回更新后的头节点 head。 图示 第一步 第二步 第三步遍历链表查找要删除的节点 第四步 代码演示
class ListNode {int val;ListNode next;ListNode(int x) {val x;}
}class Solution {public ListNode deleteNode(ListNode head, int val) {if (head null) return null; // 如果链表为空直接返回 null// 创建一个虚拟头节点方便处理头节点的删除ListNode dummy new ListNode(0);dummy.next head;ListNode pre dummy; // 前一个节点指针ListNode cur head; // 当前节点指针while (cur ! null) {if (cur.val val) { // 如果当前节点的值等于要删除的值pre.next cur.next; // 将前一个节点的指针指向当前节点的下一个节点break; // 找到并删除节点后退出循环}pre cur; // 更新前一个节点指针cur cur.next; // 更新当前节点指针}head dummy.next; // 更新头节点return head; // 返回头节点}
}public class Main {// 创建链表public static ListNode createList(int[] nums) {if (nums.length 0) return null;ListNode head new ListNode(nums[0]);ListNode cur head;for (int i 1; i nums.length; i) {cur.next new ListNode(nums[i]);cur cur.next;}return head;}// 输出链表public static void printList(ListNode head) {ListNode cur head;while (cur ! null) {System.out.print(cur.val );cur cur.next;}System.out.println();}public static void main(String[] args) {// 输入链表int[] nums {4, 5, 1, 9};ListNode head createList(nums);int val 5;// 删除指定值的节点Solution solution new Solution();head solution.deleteNode(head, val);// 输出删除后的链表printList(head);}
}
三K个一组反转链表LeetCode.25
问题描述 给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。 k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 示例 输入head [1,2,3,4,5], k 2 输出[2,1,4,3,5] 示例二 输入head [1,2,3,4,5], k 3 输出[3,2,1,4,5] 解题思路 创建一个虚拟头节点 dummy将其 next 指向原链表的头节点 head方便处理头部的特殊情况。 使用 pre 指针来记录每个需要翻转的子链表的前一个节点。初始时pre 指向虚拟头节点。 在循环中先找到需要翻转的子链表的起始节点 start 和结束节点 end。如果剩余节点不足 k 个则结束循环。 将当前子链表与下一个子链表断开即将 end-next 置为 nullptr。 调用 reverse 函数翻转当前子链表并将翻转后的子链表连接到前一个子链表的末尾即将 pre-next 指向翻转后的子链表的头节点。 将翻转后的子链表的末尾与下一个子链表的开头连接即将 start-next 指向下一个需要翻转的子链表的第一个节点。 更新 pre 指向下一个需要翻转的子链表的前一个节点。 循环直到所有子链表都被翻转。 图示 第一步 第二步 第三步 第四步 第五步 第六步 第七步 代码演示
class ListNode {int val;ListNode next;ListNode(int x) { val x; }
}class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy new ListNode(0); // 创建一个虚拟头节点方便处理头部的特殊情况dummy.next head;ListNode prev dummy; // prev 指向每个需要翻转的子链表的前一个节点while (true) {ListNode start prev.next; // start 指向当前需要翻转的子链表的第一个节点ListNode end prev; // end 指向当前需要翻转的子链表的最后一个节点for (int i 0; i k end ! null; i) {end end.next; // 找到当前需要翻转的子链表的最后一个节点}if (end null) {break; // 如果剩余节点不足 k 个结束循环}ListNode nextGroup end.next; // nextGroup 指向下一个需要翻转的子链表的第一个节点end.next null; // 将当前子链表与下一个子链表断开prev.next reverse(start); // 翻转当前子链表并将翻转后的子链表连接到前一个子链表的末尾start.next nextGroup; // 将翻转后的子链表的末尾与下一个子链表的开头连接prev start; // 更新 prev 指向下一个需要翻转的子链表的前一个节点}return dummy.next; // 返回虚拟头节点的下一个节点作为翻转后的链表的头节点}private ListNode reverse(ListNode head) {ListNode prev null;ListNode curr head;while (curr ! null) {ListNode next curr.next;curr.next prev;prev curr;curr next;}return prev;}
}public class Main {public static void main(String[] args) {ListNode head new ListNode(1);head.next new ListNode(2);head.next.next new ListNode(3);head.next.next.next new ListNode(4);head.next.next.next.next new ListNode(5);Solution solution new Solution();ListNode newHead solution.reverseKGroup(head, 2);printList(newHead); // 输出2 1 4 3 5}private static void printList(ListNode head) {ListNode curr head;while (curr ! null) {System.out.print(curr.val );curr curr.next;}System.out.println();}
}
总结 这三道链表题相比较于上篇的三道题难度有些增加因此要多加注重理解。作者在写算法题的时候也借鉴了许多技术大佬的相关博客知识和力扣官方的解题思路后续还会再写有关链表的经典算法题大家可以持续关注
