重庆网站建设策划,淘宝客网站需要多大主机,晋城门户网站建设,网站后台更新后主页不显示题目出处
92-反转链表II-题目出处
题目描述 个人解法 思路#xff1a; todo代码示例#xff1a;#xff08;Java#xff09; todo复杂度分析 todo官方解法
92-反转链表II-官方解法
前言
链表的操作问题#xff0c;一般而言面试#xff08;机试#xff09;的时候不…题目出处
92-反转链表II-题目出处
题目描述 个人解法 思路 todo代码示例Java todo复杂度分析 todo官方解法
92-反转链表II-官方解法
前言
链表的操作问题一般而言面试机试的时候不允许我们修改节点的值而只能修改节点的指向操作。
思路通常都不难写对链表问题的技巧是一定要先想清楚思路并且必要的时候在草稿纸上画图理清「穿针引线」的先后步骤然后再编码。
方法1穿针引线 思路 代码示例Java Data
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val val;}ListNode(int val, ListNode next) {this.val val;this.next next;}
}public class Solution1 {public ListNode reverseBetween(ListNode head, int left, int right) {// 因为头节点有可能发生变化使用虚拟头节点可以避免复杂的分类讨论ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;// 第 1 步从虚拟头节点走 left - 1 步来到 left 节点的前一个节点// 建议写在 for 循环里语义清晰for (int i 0; i left - 1; i) {pre pre.next;}// 第 2 步从 pre 再走 right - left 1 步来到 right 节点ListNode rightNode pre;for (int i 0; i right - left 1; i) {rightNode rightNode.next;}// 第 3 步切断出一个子链表截取链表ListNode leftNode pre.next;ListNode curr rightNode.next;// 注意切断链接pre.next null;rightNode.next null;// 第 4 步同第 206 题反转链表的子区间reverseLinkedList(leftNode);// 第 5 步接回到原来的链表中pre.next rightNode;leftNode.next curr;return dummyNode.next;}private void reverseLinkedList(ListNode head) {// 也可以使用递归反转一个链表ListNode pre null;ListNode cur head;while (cur ! null) {ListNode next cur.next;cur.next pre;pre cur;cur next;}}}复杂度分析 时间复杂度O(N)其中 N 是链表总节点数。最坏情况下需要遍历整个链表。空间复杂度O(1)。只使用到常数个变量。
方法2:一次遍历「穿针引线」反转链表头插法 思路 代码示例Java public class Solution2 {public ListNode reverseBetween(ListNode head, int left, int right) {// 设置 dummyNode 是这一类问题的一般做法ListNode dummyNode new ListNode(-1);dummyNode.next head;ListNode pre dummyNode;for (int i 0; i left - 1; i) {pre pre.next;}ListNode cur pre.next;ListNode next;for (int i 0; i right - left; i) {next cur.next;cur.next next.next;next.next pre.next;pre.next next;}return dummyNode.next;}}复杂度分析 时间复杂度O(N)其中 N 是链表总节点数。最多只遍历了链表一次就完成了反转。空间复杂度O(1)。只使用到常数个变量。
考察知识点
收获
Gitee源码位置
92-反转链表II-源码
