141. 环形链表
判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。
/**
* 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) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
};142. 环形链表 II
判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL) {
return NULL;
}
ListNode* slow = head;
ListNode* fast = head;
while (true) {
// 如果没有环，直接返回
if (fast == NULL || fast->next == NULL) {
return NULL;
}
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break;
}
}
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
};876. 链表的中间结点
快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。
- 当链表的长度是奇数时，slow 恰巧停在中点位置；
- 如果长度是偶数，slow 最终的位置是中间偏右
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};19. 删除链表的倒数第 N 个结点
先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* findNthFromEnd(ListNode* head, int n) {
ListNode* slow = head;
ListNode* fast = head;
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = findNthFromEnd(dummy, n + 1);
pre->next = pre->next->next;
return dummy->next;
}
};674. 最长连续递增序列
思路分析：
题目要求我们找的子序列是 连续 的，并且子序列里的元素要求 严格单调递增。在遍历的时候，从第 2 个元素开始；
- 如果当前遍历到的元素比它左边的那一个元素要严格大，「连续递增」的长度就加 1；
- 否则「连续递增」的起始位置就需要重新开始计算。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int len = nums.size();
int left = 0, right = 0;
int res = 0;
while (right < len) {
if (right > 0 && nums[right-1] >= nums[right]) {
left = right;
}
right++;
res = max(res, right - left);
}
return res;
}
};26. 删除有序数组中的重复项
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int left = 0, right = 0;
while (right < nums.size()) {
if (nums[right] > nums[left]) {
left++;
nums[left] = nums[right];
}
right++;
}
return left + 1;
}
};80. 删除有序数组中的重复项 II
class Solution {
public:
int removeDuplicatesK(vector<int>& nums, int k) {
int len = nums.size();
if (len <= k) {
return len;
}
int slow = k;
for (int fast = k; fast < len; ++fast) {
if (nums[fast] != nums[slow - k]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
int removeDuplicates(vector<int>& nums) {
return removeDuplicatesK(nums, 2);
}
};283. 移动零
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0,right = 0;
while (right < nums.size()) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
right++;
}
return left;
}
void moveZeroes(vector<int>& nums) {
int index = removeElement(nums, 0);
for (; index < nums.size(); ++index) nums[index] = 0;
}
};
