目录
二、103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）
三、33. 搜索旋转排序数组 - 力扣（LeetCode）?
四、88. 合并两个有序数组 - 力扣（LeetCode）?
一、141. 环形链表 - 力扣（LeetCode）
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递?。仅仅是为了标识链表的实际情况。
如果链表中存在环?，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例?2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
?提示：
链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。
思路
快慢指针。前面写过这道题，所以比较快的想到了这个方法。
快指针一直走在慢指针的前面，但是如果链表存在环的话，两个指针最终会相遇，因此判断链表存在环。
代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL||head->next==NULL)
{
return false;
}
ListNode* p;
ListNode* q;
p=head;
q=head;
while(p!=NULL&&p->next!=NULL)
{
p=p->next->next;
q=q->next;
if(p==q)
{
return true;
}
}
return false;
}
};二、103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）
题目描述
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：输入：root = [1]
输出：[[1]]
示例 3：输入：root = []
输出：[]
?提示：
树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100
思路：
大致和普通的层序遍历类似。因为要一层一层交替，所以当在层数为奇数的时候（因为我是先遍历右孩子，如果先遍历左孩子也可以，那就是层数为偶数的时候），需要将这一层的遍历结点的顺序逆置。如果层数为偶数时，就正常放入vector数组即可。
代码实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
int x=1;//记录层数
vector<vector<int>> a;
queue<TreeNode*> q;
if(root!=NULL)
{
q.push(root);
}
while(!q.empty())
{
vector<int> b;
int size=q.size();
while(size--)
{
if(q.front()->right)//先遍历右孩子
{
q.push(q.front()->right);
}
if(q.front()->left)//再遍历左孩子
{
q.push(q.front()->left);
}
b.push_back(q.front()->val);
q.pop();
}
if(x%2!=0)//当层数（从0开始）是奇数时，对于队列中的结点，先遍历右孩子再遍历左孩子会使它的顺序逆着，所以需要将它逆置。
{
vector<int> c;
for(int i=b.size()-1;i>=0;i--)//逆置
{
c.push_back(b[i]);
}
a.push_back(c);
}
else
{
a.push_back(b);
}
x++;//层数加一
}
return a;
}
};三、33. 搜索旋转排序数组 - 力扣（LeetCode）?
题目描述
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为?[4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回?-1?。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例?2：输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
示例 3：输入：nums = [1], target = 0
输出：-1
?提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
思路
这题的难点在于时间复杂度要为O(log n)。直接从前往后遍历数组，肯定超时，所以利用双指针，时间复杂度就可以满足条件了。
代码实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int i=0,j=nums.size()-1;
while(i<=j)
{
if(nums[i]==target)
{
return i;
}
else if(nums[j]==target)
{
return j;
}
else
{
i++;
j--;
}
}
return -1;
}
};四、88. 合并两个有序数组 - 力扣（LeetCode）?
题目描述
给你两个按?非递减顺序?排列的整数数组?
nums1?和?nums2，另有两个整数?m?和?n?，分别表示?nums1?和?nums2?中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
?提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9
思路
注意，这一题是要将nums2合并到nums1中，不能另外开一个数组。因为nums1后面有空余的空间，所以，从后面往前进行比较，可以不用进行元素的移动，因此时间复杂度也就降低了。起初，用3个指针，分别指向nums1数组的末尾（n+m)，nums1数组的元素的末尾（m)，nums2数组的末尾（n)，依次往前遍历，谁大谁就放入该位置。最后nums1有剩余的话，不用管。如果是nums2有剩余，就得将nums2所有剩余元素放入nums1。
代码实现
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
if(nums1.size()==0)
{
for(int i=0;i<nums2.size();i++)
{
nums1[i]=nums2[i];
}
}
else
{
int i=m,j=n,k=m+n;
while(i>0&&j>0)
{
if(nums1[i-1]>=nums2[j-1])
{
k--;
i--;
nums1[k]=nums1[i];
}
else
{
k--;
j--;
nums1[k]=nums2[j];
}
}
while(j)
{
k--;
j--;
nums1[k]=nums2[j];
}
}
}
};