Leetcode解题思想总结篇:双指针 – BYRHuangQiang

Leetcode解题思想总结篇:双指针

1概念

双指针:快慢指针。
快指针在每一步走的步长要比慢指针一步走的步长要多。快指针通常的步速是慢指针的2倍。

在循环中的指针移动通常为:
faster = faster.next.next; slower = slower.next;

2 应用

2.1. 用来判断链表是否有环以及寻找环入口

  • Linked List Cycle
  • Linked List Cycle II

是否有环:快慢指针思想,注意循环条件:(fast != null) && (fast.next != null)

寻找环的入口:快慢指针相遇的时候,distance(fast指针) = 2 * distance(slow指针),可以推导出,只要把fast重新指向头结点,两个指针以一样的速度走,相遇的时候,便是环的入口。

2.2.数组寻找范围

  • Summary Ranges

范围的寻找,用2个指针:startend来记录范围。注意循环条件和判断条件:(end + 1 < len) && (nums[end + 1] == nums[end] + 1)

2.3.链表或者数组中移除重复的元素

  • Remove Duplicates from Sorted List I
  • Remove Duplicates from Sorted List II

Sorted List I用两个指针一前一后指向链表。维护两个指针:

  • tail 一个指向当前不重复的最后一个元素,
  • pCur 一个进行依次扫描,遇到不重复的则更新第一个指针,继续扫描,否则就把前面指针指向当前元素的下一个(即把当前元素从链表中删除)。

Sorted List II 维护两个指针:

  • prev前驱指针指向上一个不重复的元素
  • pCur遍历指针
    思路类似Sorted List I,细节更多。
    寻找不重复的元素 while循环条件pCur.next != null && prev.next.val == pCur.next.val

Array数组中的解题思想一样:

  • index指向上当前不重复的最后一个元素
  • i遍历数组

2.4. 用来找中点或中位数

2.5. 倒数第n个

题目中含有:倒数第n个,那么设置快指针步长为n,然后快慢指针同时以同一速度走,用慢指针寻找倒数第n个

2.6. 拆分链表

Partition List

给定一个x的值,小于x都放在大于等于x的前面,并且不改变链表之间node原始的相对位置。example中 4->3->5都是大于等3的数,这保持了他们原来的相对位置。

使用链表最常用的双指针:

  • 一个指向当前小于x的最后一个元素
  • 一个进行往前扫描。如果元素大于x,那么继续前进,否则,要把元素移到前面,并更新第一个指针。

Reorder List

思路:
1.利用快慢两个指针将链表一分为二;
2.针对第二个子链表求倒序;
3.利用merge思想将两个子链表合并。

3 相关题目

4 注意

  1. 通常需要特别留意链表长度的奇偶性
  2. 如果快指针步速为慢指针步速2倍,循环条件为:faster.next!=null && faster.next.next!=null
  3. 当自行设置快指针步长时, 要考虑步长值等于链表长度的特殊情况
  4. 查找倒数第n个时,如果要求删除链表元素时,不要忘记记录应被删除元素的前一个元素
  5. 对于链表的题目,常常都会用到Two Pointers的思想。链表注意构建dummy头结点。在Java中,由于没有free函数,所以在删除一个节点的时候,无法用node = null来删除一个节点,需要用前一个节点来指向删除节点的下一个prev.next = node.next这样来删除node节点。

5 参考

本文链接:Leetcode解题思想总结篇:双指针,转载请注明。



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量