牛客刷题系列之进阶版（搜索旋转排序数组，链表内指定区间反转）

@[toc](每日一题)
> 很多小伙伴为了刷题发愁
> 今天为大家推荐一款刷题神奇哦：[刷题面试神器牛客](https://www.nowcoder.com/link/pc_csdncpt_xfh_sf)
> 各大互联网大厂面试真题。从基础到入阶乃至原理刨析类面试题 应有尽有，赶快来装备自己吧！助你面试稳操胜券，solo全场面试官


# 一：搜索旋转排序数组
## 1.题目
[题目链接](https://leetcode.cn/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/)


## 2.代码实现

```cpp
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right =nums.size()-1;
        int mid;
        while(left<=right)
        {
            mid = (left+right)/2;

            if(nums[0]>target)//当t在右边的数组时
            {
                if(nums[mid]>=nums[0]) //当mid左边时，需要将left=mid+1
                nums[mid] = -10001;
            }
            else//当t在左边的数组时
            {
                if(nums[mid] < nums[0]) //当mid右边时，需要将right = mid-1;
                 nums[mid] = 10001;
            }

            if(nums[mid] > target)
               right = mid-1;
            else if(nums[mid] <target)
              left = mid+1;
              else
              return mid;
        }
         return -1;
    }
};
```

## 3.思路和注意事项
* 思路是模拟二分查找来实现的
1. 普通的二分查找是 
    if(nums[mid] > target)
               right = mid-1;
            else if(nums[mid] <target)
              left = mid+1;
              else
              return mid;
 2. nums[mid] > target时，   right = mid-1; 所以我们可以用 nums[mid] = 10001;来模拟 这种情况。
 3. 当我们找到在特殊情况下的right 要变成mid-1时，我们就可以用 nums[mid] = 10001;来模拟 这种情况。
 4. 具体的情况看代码注释（主要是看mid和t在哪一边）
  


# 二：链表内指定区间反转
## 1.题目
[题目链接](https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c?tpId=188&&tqId=38555&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking)

## 2.代码实现

```cpp
/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode* res =new ListNode(0);
        ListNode* cur = head;
        ListNode* pre = res;
        res->next= head;
        for(int i=1;i<m;i++)
        {
            pre =cur;
            cur =cur->next;
        }
        for(int i=m;i<n;i++)
        {
           ListNode* tem =cur->next;
            cur->next = tem->next;
            tem->next  =   pre->next;
            pre->next = tem;
        }
        return res->next;;
    }
};
```

## 3.思路和注意事项

> 主要思路就是一次一次的反转
* 需要注意的是要设虚拟头节点，以防头节点的改变的情况
# ps

> 想和博主一样刷优质面试和算法题嘛，快来[刷题面试神器牛客](https://www.nowcoder.com/link/pc_csdncpt_xfh_sf)吧，期待与你在牛客相见