给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null || head.next == null) return false;
//快慢双指针，同时出发
ListNode slow = head,fast=slow;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(fast==slow){
return true;
}
}
return false;
}
}给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null||head.next==null) return null;
ListNode slow=head,fast=slow;
boolean hasCycle = false;
while(fast!=null&&fast.next!=null){
slow=slow.next;
fast=fast.next.next;
if(fast==slow){//如果有环，跳出循环
hasCycle=true;break;
}
}
if(hasCycle==false) return null;
//任选一个回到头节点，一步一步走
slow=head;
while(fast!=slow){
fast=fast.next;slow=slow.next;
}
return slow;
}
}双指针技巧主要分为两类：快慢指针和左右指针
快慢指针 ​
26. 删除有序数组中的重复项 ​
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。返回
k。示例 1：
输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
class Solution {
public int removeDuplicates(int[] nums) {
//快慢指针同时从0出发
int slow=0,fast=0;
//快指针在前面探路，找我们想要的不重复元素
while(fast<nums.length){
if(nums[slow]!=nums[fast]){
slow++;
nums[slow]=nums[fast];
}
fast++;
}
return slow+1;
}
}27. 移除元素 ​
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。class Solution {
public int removeElement(int[] nums, int val) {
//快慢指针同时出发
int slow=0,fast=0;
//快指针在前面探路，找我们想要的不为val的元素
while(fast<nums.length){
if(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}
fast++;
}
return slow;
}
}206. 反转链表 ​
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
ListNode tmp;
while(cur!=null){
tmp = cur.next;
cur.next = pre;//反转
pre = cur;
cur = tmp;
}
return pre;
}
}面试题 02.02. 返回倒数第 k 个节点 ​
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4class Solution {
public int kthToLast(ListNode head, int k) {
ListNode slow = head,fast=head;
while(k-->0){//fast先走k步
fast=fast.next;
}
while(fast!=null){
slow=slow.next;
fast=fast.next;
}
return slow.val;
}
}19. 删除链表的倒数第 N 个结点 ​
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//使用虚拟头节点，方便删除操作
ListNode dummyHead=new ListNode(-1,head);
ListNode fast = dummyHead,slow=fast;
n=n+1;//找到倒数第n+1个节点，然后删除它的下一个
while(n-->0){
fast=fast.next;
}
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
//删除节点
slow.next=slow.next.next;
return dummyHead.next;
}
}160. 相交链表 ​
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA=headA,curB=headB;
while (curA != curB) {
curA=curA==null?headB:curA.next;
curB=curB==null?headA:curB.next;
}
return curA;
}
}左右指针 ​
344. 反转字符串 ​
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]class Solution {
public void reverseString(char[] s) {
int left=0,right=s.length-1;
while(left<right){
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;right--;
}
}
}704. 二分查找 ​
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0,right = len-1;
while(left<=right){
int mid = (right-left)/2+left;
if(nums[mid]==target) return mid;
else if(nums[mid]<target) left=mid+1;
else if(nums[mid]>target) right=mid-1;
}
return -1;
}
}15. 三数之和 ​
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//排序，为了排除情况，和后面用二分法
Arrays.sort(nums);//-4, -1, -1, 0, 1, 2
if(nums[0]>0) return new ArrayList<>();
//放到Set里去重
Set<List<Integer>> res = new HashSet<>();
for (int i = 0; i < nums.length-2; i++) {
int target = -nums[i];
//在数组种寻找sum为target的组合
int left = i + 1, right = nums.length - 1;
while (left < right) {//二分查找
int sum = nums[left] + nums[right];
if (sum == target) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
} else if (sum < target) {//说明太小了
left++;
} else right--;
}
}
return new ArrayList<>(res);
}
}3. 无重复字符的最长子串 ​
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。class Solution {
public int lengthOfLongestSubstring(String s) {
int left=0,right=0;
int res=0;
HashMap<Character, Integer> window = new HashMap<>();
while(right<s.length()){
char in = s.charAt(right++);//进窗口
window.put(in, window.getOrDefault(in, 0) + 1);
while(window.get(in)>1){//说明重复了
char out=s.charAt(left++);//出窗口
window.put(out,window.get(out)-1);
}
res=Math.max(res,right-left);
}
return res;
}
}