题目链接：环形链表 II给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。方法一：哈希表/** * 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) { unordered_set<ListNode*> m; ListNode* t = head; while (t) { if (m.count(t)) { return t; } m.insert(t); t = t->next; } return NULL; } };方法二：快慢指针class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast != nullptr) { slow = slow->next; if (fast->next == nullptr) { return nullptr; } fast = fast->next->next; if (fast == slow) { ListNode *ptr = head; while (ptr != slow) { ptr = ptr->next; slow = slow->next; } return ptr; } } return nullptr; } };
题目链接：盛最多水的容器给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。方法：双指针class Solution { public: int maxArea(vector<int>& height) { int ans = 0; int l = 0,r = height.size()-1; while (l < r) { ans = max(ans,min(height[r],height[l])*(r-l)); if (height[r] > height[l]) { l++; }else { r--; } } return ans; } };
题目链接：移动零给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。方法：哈希表class Solution { public: void moveZeroes(vector<int>& nums) { int n = nums.size(),l = 0,r = 0; while (r < n) { if (nums[r]) { swap(nums[l],nums[r]); l++; } r++; } } };