算法(五) 快慢指针
快慢指针方法也被称为 Hare & Tortoise 算法，该算法会使用两个在数组（或序列/链表）中以不同速度移动的指针。
该方法在处理循环链表或数组时非常有用。
例题
1，环形链表
来自LeetCode 141
解法
1，哈希表
有空再补吧。哈希表忘差不多了哈哈哈。
2，快慢指针
- 将两个指针置于相同的位置，赋予后指针更慢的数字，前指针更快的速度。
- 如果非环，则到null都永远碰不上。
- 如果是环，则迟早会撞上。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null||head.next==null){
return false;
}
ListNode fr = head;
ListNode be = head.next;
while(fr!=be){
if(fr==null||be==null)
return false;
fr = fr.next;
if(be.next==null)
return false;
be = be.next.next;
}
return true;
}
}理解
1，对于链表题，总要涉及next，本题因为速度不同，出现next.next，这样就必须要考虑前一个next为空对象的情况。
2,链表中倒数第k个节点
来自剑指offer22.
这道题是快慢指针的智力用法，想到思路就很容易解决。
解法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fr = head;
ListNode be = head;
for(int i = 0;i<k;i++){
if(be.next==null)
return head;
be = be.next;
}
while(be!=null){
fr=fr.next;
be=be.next;
}
return fr;
}
}理解
1，思路很重要！！！
2，链表应该优先想到双指针和迭代，快慢指针是双指针中很基础的解法。
3,回文链表
来自LeetCode234
本题掌握非常差，务必重新做一次！！！！！
解法
1，快慢指针 + 栈
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head.next==null)
return true;
ListNode fr = head;
ListNode br = head;
ListNode cur = null;
Stack<ListNode> stack = new Stack<ListNode>();
while(br!=null){
stack.push(fr);
cur = fr;
fr = fr.next;
if(br.next==null){
br = null;
stack.pop();
fr = cur;
}
else if(br.next.next!=null)
br = br.next.next;
else{
br = null;
fr = cur;
}
}
fr = fr.next;
while(fr!=null){
ListNode a = stack.peek();
if(fr.val != a.val)
return false;
stack.pop();
fr = fr.next;
}
return stack.isEmpty();
}
}快慢指针：用于寻找中点
- 前指针和后指针同时位于head，前指针next速度，后指针next.next的速度。
- 当后指针为null或者next为空时，前指针到中点。
- 这是快慢指针的常见用法。
栈：懂得都懂。
理解
- 本题快慢指针的中点查找的边界值，俺的算法有巨大问题，务必重新研究一遍！！！！！！！！！。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-08-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
