力扣实训 _ [33].搜索旋转排序数组 _ [92].翻转链表Ⅱ

33.搜索旋转排序数组在力扣的算法题库中“搜索旋转排序数组”是一道非常经典的二分查找变体题。很多同学在遇到“旋转”这个条件时往往会觉得无法直接使用二分查找。今天我们就来详细拆解这道题带你掌握如何在看似无序的数组中依然能够运用二分思想实现 O(log n) 的高效查找。1. 题目回顾假设有一个严格升序排列的数组在某个未知的下标处进行了旋转例如[0,1,2,4,5,6,7]旋转后变为[4,5,6,7,0,1,2]。现在给定这个旋转后的数组nums和一个目标值target要求返回target的下标如果不存在则返回 -1。核心要求算法的时间复杂度必须控制在 O(log n)。2. 核心思路寻找“局部有序”面对 O(log n) 的时间复杂度要求我们首先想到的就是二分查找。虽然数组整体被旋转打乱了顺序但它有一个极其重要的特性无论我们从哪个位置将数组一分为二其中至少有一半是严格有序的。比如[4,5,6,7,0,1,2]如果我们从中间切开左半部分[4,5,6]是有序的右半部分[7,0,1,2]是无序的或者换个切法右半部分有序左半部分无序。解题的关键就在于在二分的过程中判断哪一半是有序的并进一步判断目标值是否在这个有序区间内从而决定下一步的搜索方向。3. 算法详细步骤初始化指针设置left 0right nums.length - 1。进入二分循环当left right时持续执行。计算中点mid left (right - left) / 2防止整型溢出。命中检查如果nums[mid] target直接返回mid。判断有序区间并收缩边界情况一左半部分有序即nums[left] nums[mid]如果target刚好落在左侧有序区间内nums[left] target nums[mid]说明目标在左边收缩右边界right mid - 1。否则目标在右边收缩左边界left mid 1。情况二右半部分有序即nums[left] nums[mid]如果target刚好落在右侧有序区间内nums[mid] target nums[right]说明目标在右边收缩左边界left mid 1。否则目标在左边收缩右边界right mid - 1。4. 代码实现Java KotlinJava版本class Solution { public int search(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { // 计算中间下标防止 (left right) 溢出 int mid left (right - left) / 2; // 1. 命中目标值直接返回 if (nums[mid] target) { return mid; } // 2. 判断左半部分 [left, mid] 是否有序 if (nums[left] nums[mid]) { // 左半部分有序判断 target 是否在左侧区间内 if (nums[left] target target nums[mid]) { right mid - 1; // 在左侧收缩右边界 } else { left mid 1; // 不在左侧去右侧找 } } // 3. 否则右半部分 [mid, right] 一定有序 else { // 右半部分有序判断 target 是否在右侧区间内 if (nums[mid] target target nums[right]) { left mid 1; // 在右侧收缩左边界 } else { right mid - 1; // 不在右侧去左侧找 } } } // 循环结束未找到返回 -1 return -1; } }Kotlin版本class Solution { fun search(nums: IntArray, target: Int): Int { var left 0 var right nums.size - 1 while (left right) { val mid left (right - left) / 2 if (nums[mid] target) { return mid } // 判断左半部分是否有序 if (nums[left] nums[mid]) { if (nums[left] target target nums[mid]) { right mid - 1 } else { left mid 1 } } else { // 右半部分有序 if (nums[mid] target target nums[right]) { left mid 1 } else { right mid - 1 } } } return -1 } }5. 复杂度分析时间复杂度O(log n)。每次循环都将搜索区间缩小一半符合二分查找的标准复杂度。空间复杂度O(1)。只使用了left、right、mid等常数级别的额外空间。92.翻转链表Ⅱ相比于完全反转整个链表这道题要求我们只反转链表中的指定区间[left, right]这非常考验对链表指针操作的细节把控。1.题目回顾给你单链表的头指针head和两个整数left和right其中left right。请你反转从位置left到位置right的链表节点并返回反转后的链表。示例输入head [1,2,3,4,5],left 2,right 4输出[1,4,3,2,5]2.核心思路穿针引线法这道题的核心在于将链表分为三个部分未反转的前半段、需要反转的区间、未反转的后半段。我们只需要把中间那段反转再重新把这三段“缝合”起来即可。具体步骤如下引入虚拟头节点Dummy Node因为left有可能是1即从头节点开始反转为了避免对头节点进行复杂的特判我们创建一个虚拟头节点dummy让dummy.next head。定位前驱节点p0我们需要找到反转区间的前一个节点即left - 1位置的节点记为p0。它将是连接“前半段”和“反转后区间”的关键锚点。局部反转区间从p0.next开始对区间内的right - left 1个节点进行标准的链表反转操作。重新连接链表反转结束后我们需要把断开的链表接回去原反转区间的第一个节点反转后变成了区间的最后一个节点它的next应该指向后半段的第一个节点。前驱节点p0的next应该指向反转后区间的新头节点。3.算法详细步骤与图解假设链表为1 - 2 - 3 - 4 - 5left 2,right 4。准备阶段创建dummy(0) - 1 - 2 - 3 - 4 - 5。移动p0到left - 1的位置此时p0指向节点1。反转准备cur指向反转区间的第一个节点节点2。pre初始化为null用于反转过程中的前驱记录。执行局部反转循环right - left 1次使用标准的“三指针法”反转2 - 3 - 4这段链表。反转结束后pre指向节点4新区间的头cur指向节点5后半段的头而原来的p0.next节点2变成了新区间的尾。缝合链表p0.next.next cur让节点2指向节点5。p0.next pre让节点1指向节点4。最终得到1 - 4 - 3 - 2 - 5。4.代码实现Java KotlinJava版本/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { // 1. 创建虚拟头节点简化 left1 时的边界情况处理 ListNode dummy new ListNode(0, head); // 2. 找到反转区间的前驱节点 p0 (即 left - 1 位置的节点) ListNode p0 dummy; for (int i 0; i left - 1; i) { p0 p0.next; } // 3. 开始反转区间 [left, right] 内的节点 // pre 用于记录反转后的前驱cur 指向当前要反转的节点初始为 left 位置的节点 ListNode pre null; ListNode cur p0.next; // 需要反转的节点数量为 right - left 1 for (int i 0; i right - left 1; i) { ListNode nxt cur.next; // 暂存 cur 的后继节点防止断链 cur.next pre; // 反转当前节点的指针 pre cur; // pre 指针后移 cur nxt; // cur 指针后移 } // 4. 重新连接链表 // 此时 // - pre 指向反转区间的新头节点原 right 位置的节点 // - cur 指向反转区间后面的第一个节点即后半段的头 // - p0.next 指向原反转区间的第一个节点反转后变成了区间的尾节点 // 让原反转区间的第一个节点现尾部指向后半段的头节点 p0.next.next cur; // 让前驱节点 p0 指向反转后的新头节点 p0.next pre; // 5. 返回新链表的头节点 return dummy.next; } }Kotlin版本/** * Definition for singly-linked list. * class ListNode(var val: Int) { * var next: ListNode? null * } */ class Solution { fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? { // 1. 创建虚拟头节点指向原链表头简化 left1 时的边界处理 val dummy ListNode(0) dummy.next head // 2. 找到反转区间的前驱节点 p0 (即 left - 1 位置的节点) var p0: ListNode? dummy for (i in 0 until left - 1) { p0 p0?.next } // 3. 开始局部反转区间 [left, right] 内的节点 // pre 用于记录反转后的前驱cur 指向当前要反转的节点初始为 left 位置的节点 var pre: ListNode? null var cur: ListNode? p0?.next // 需要反转的节点数量为 right - left 1 for (i in 0 until right - left 1) { val nxt cur?.next // 暂存 cur 的后继节点防止断链 cur?.next pre // 反转当前节点的指针 pre cur // pre 指针后移 cur nxt // cur 指针后移 } // 4. 重新连接链表缝合操作 // 此时 // - pre 指向反转区间的新头节点原 right 位置的节点 // - cur 指向反转区间后面的第一个节点即后半段的头 // - p0?.next 指向原反转区间的第一个节点反转后变成了区间的尾节点 // 让原反转区间的第一个节点现尾部指向后半段的头节点 p0?.next?.next cur // 让前驱节点 p0 指向反转后的新头节点 p0?.next pre // 5. 返回新链表的头节点跳过虚拟头节点 return dummy.next } }5.复杂度分析时间复杂度O(n)。其中 n 是链表的长度。我们只需要遍历一次链表先走到left前驱再反转指定区间整体是线性的。空间复杂度O(1)。我们只使用了dummy,p0,pre,cur等固定数量的指针变量没有使用额外的数组或递归栈空间。