leetcode高频题笔记之双指针
在许多数组和链表的题中，都需要用到双指针的思想来优化，本文总结归纳了几种常见的双指针和对应的应用案例，通过针对的性的刷题希望能熟练的掌握双指针的运用
167.两数之和II-输入有序数组（头尾指针）
定义两个指针，一个是头指针i，一个是尾指针j
判断 numbers[i]+numbers[j]与target的值大大小
如果相等，就返回下标+1的数组
如果target更大，说明数小了，i向后移
如果target更小，说明数大了，j向前移
public class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0;
int j = numbers.length - 1;
int sum;
while (i < j) {
sum = numbers[i] + numbers[j];
if (sum == target) return new int[]{i + 1, j + 1};
else if (sum > target) j--;
else i++;
}
return new int[0];
}
} 633.平方数之和（头尾指针）
a和b的取值在0到(int)Math.sqrt(c)之间
所以就以这两个值为上下界进行双指针遍历
public class Solution {
public boolean judgeSquareSum(int c) {
int i = 0;
int j = (int) Math.sqrt(c);
while (i <= j) {
int tmp = i * i + j * j;
if (tmp == c) return true;
else if (tmp > c) j--;
else i++;
}
return false;
}
} 345.反转字符串中的元音字母（头尾指针）
题目的意思是将字符串的正数第n个元音字母和倒数第n个元音字母交换
定义头指针i和尾指针j
定义一个char类型的数组
从头尾同时遍历，如果不是元音就直接加入新数组，如果是元音就等到两端都是元音了然后交换写入数组
public class Solution {
public String reverseVowels(String s) {
int i = 0;
int j = s.length() - 1;
char news[] = new char[s.length()];
Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
while (i <= j) {
char ci = s.charAt(i);
char cj = s.charAt(j);
if (!set.contains(ci)) news[i++] = ci;
else if (!set.contains(cj)) news[j--] = cj;
else {
news[i++] = cj;
news[j--] = ci;
}
}
return new String(news);
}
} 680.验证回文字符串Ⅱ（头尾指针）
定义头指针i和尾指针j
从头尾开始遍历，如果相等同时向中间缩进
如果发现不等，尝试删去i所在数和j所在数
删除后继续遍历，如果有任意一种情况能走完就符合回文字符串
public class Solution {
public boolean validPalindrome(String s) {
int i = 0;
int j = s.length() - 1;
while (i < j) {
if (s.charAt(i) == s.charAt(j)) {
i++;
j--;
} else {
return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
}
}
return true;
}
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i++) != s.charAt(j--)) return false;
}
return true;
}
} 88.合并两个有序数组（异步指针）
从数组的尾部开始
定义一个指针k从新数组的最后一个位置开始
指针m，n分别从两个数组的最后一个数的位置开始
比较两个数组最后一个数的大小，大的放在新数字的指针处
如果有个数组指针为0了，判断是否是n的，如果是m就直接有序不需要处理，如果是n就依次填入新数组的位置
public class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int k = m-- + n-- - 1;
while (m >= 0 && n >= 0) {
nums1[k--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
}
while (n >= 0) {
nums1[k--] = nums2[n--];
}
}
} 21.合并两个有序链表（异步指针）
从头部开始
定义前驱指针pre
定义迭代的指针node = pre
判断连个指针l1和l2的值，把小的赋值给node.next
当迭代到有一个为空时，判断一下，把不为空的接在最后
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(-1);
ListNode node = pre;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
node.next = l1;
l1 = l1.next;
node = node.next;
} else {
node.next = l2;
l2 = l2.next;
node = node.next;
}
}
if (l1 == null) node.next = l2;
else node.next = l1;
return pre.next;
}
} 141.环形链表（快慢指针）
定义快指针fast和慢指针slow
fast一次走两步，slow一次走一步
关于为什么将fast设置为head.next：其实快慢指针中fast是head或者head.next都可以找到环，因为我们这里判断的是fast==slow，所以为了简化代码就保证他们初始就不一致，一旦一致就是有环
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}
} fast = head版本
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
} 142.环形链表II（快慢指针）
思路：
- 先和环形链表I一样判断有没有环，有才进行第二步
- 从同一起点开始，fast一次走两步，slow一次走一步，当他们相遇之后，fast回到原点一次走一步，第二次相遇节点就是环连接点
- 我的理解：
- 假设第二圈发生第一次相遇，第二圈走完了就第二次相遇了
- 第一次相遇时fast走了F+(a+b)+a
- slow走了F+a
- 因为fast是slow的两倍速度，所以第二次相遇时应该满足fast=2*slow
- 设slow还需要走 x远第二次相遇，可得方程
（F+2a+b+2x）=2(F+a+x),，解得F=b - 所以就假设fast以一倍的速度陪slow走完b，另一倍速从F出发，当fast与slow相遇时，相当于fast走过了b+F = 2b = 2倍slow的距离
- 此时满足第二次相遇的情况
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while (true) { if (fast == null || fast.next == null) return null; fast = fast.next.next; slow = slow.next; if (fast == slow) break;//找到第一次相遇 } fast = head;//将fast移动到head while (fast != slow) { fast = fast.next; slow = slow.next; }//第二次相遇 return fast; } }
19.删除链表的倒数第N个节点（快慢指针）
本题也运用到了快慢指针，说明快慢指针在链表题中的地位
本题思路：
- 移动快指针n步，使快慢指针步差为n
- 如果此时快指针为null，说明要删除的节点是头结点，直接返回head.next;
- 如果快指针不是null，那么就通过快慢指针查找到倒数第k+1个节点
- 然后删除掉倒数第k个节点
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null || head.next == null) return null;
ListNode fast = head;
ListNode slow = head;
//将fast和slow的步调差调成n，当fast到达末尾了，slow到达指定节点
while (n-- > 0) {
fast = fast.next;
}
//倒数的数就是头结点的情况，此时fast是null
if (fast == null){
return head.next;
}
//倒数的数不是头结点，按顺序移动fast和slow节点，直到倒数第二个，测试slow节点到达删除节点的上一个
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
//slow是待删除节点上一个节点，删除slow.next节点
slow.next = slow.next.next;
return head;
}
} 234.回文链表（快慢指针）
O(n) 时间复杂度和 O(1) 空间复杂度解法：
- 快慢指针找到中点
- 将链表分割为两部分
- 选择后一半进行翻转
- 翻转后再次比较
public class Solution {
/**
* 快慢指针找到中点
* 选择一半进行翻转
* 翻转后再次比较
*/
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null) slow = slow.next;//偶数个结点，让slow指向下一个，作为后半段的开头
//将链表分为以head和slow开头的等长的两段
cut(head, slow);
return isEqual(head, reverse(slow));
}
//翻转链表
private ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode tmp = head.next;
head.next = newHead;
newHead = head;
head = tmp;
}
return newHead;
}
//判定两个链表是否相等
private boolean isEqual(ListNode head1, ListNode head2) {
while (head1 != null && head2 != null) {
if (head1.val != head2.val) return false;
head1 = head1.next;
head2 = head2.next;
}
return true;
}
//分割链表
private void cut(ListNode head, ListNode slow) {
while (head.next != slow) {
head = head.next;
}
head.next = null;
}
} leetcode分类题集 文章被收录于专栏
按知识点分类整理leetcode的题目和解法
投递华为等公司10个岗位 >
