算法概述
Floyd循环检测算法,也被称为龟兔赛跑算法,或者快慢指针,是一种可以在链表或数组等线性结构中使用的技术。
此技术通过同时使用两个指针,一个快指针和一个慢指针来遍历一个数据结构。通常来说,快指针每次移动两个节点,而慢指针每次只移动一个节点。
它的主要优点是它可以在单次遍历中解决以上的问题,从而使得算法效率高。
在使用快慢指针时,通常需要注意的是可能出现的边界条件,例如链表为空或只有一个或两个节点的情况。
三个例子
1. 找到链表的中点
首先创建两个指针,slowPtr
和fastPtr
,都初始化为头节点。
然后,只要fastPtr
和fastPtr.next
不为null,就将fastPtr
向前移动两个节点,slowPtr
向前移动一个节点。
当fastPtr
无法再前进时,slowPtr
将位于链表的中点。
Java实现:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
next = null;
}
}
public Node findMiddle(Node head) {
Node slowPtr = head;
Node fastPtr = head;
if (head != null) {
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
}
}
return slowPtr;
}
2. 检测链表中是否有环
首先创建两个指针,slow
和fast
。slow
指针每次移动一个节点,fast
指针每次移动两个节点。
如果在某个时刻,slow
和fast
指向同一节点,那么链表中存在环。
如果fast
指针到达链表的末尾(即fast
或fast.next
为null),那么链表中不存在环。
Java实现:
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
next = null;
}
}
public boolean hasCycle(Node head) {
if (head == null) {
return false;
}
Node slow = head;
Node fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
3. 找到两个链表的交叉点
找到两个链表交叉点通常包括3个步骤:
- 我们将遍历两个链表以确定他们的长度及是否相交。
- 我们将使两个指针同时从两个链表的头部开始,但是较长的那个链表的指针会先移动“长度差”的步数。
- 两个指针将同时移动,当他们相遇时,那个点就是链表的交叉点。
Java实现:
static class ListNode {
int data;
ListNode next;
ListNode(int data) {
this.data = data;
next = null;
}
}
public ListNode getIntersectionListNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode p1 = headA;
ListNode p2 = headB;
int length1 = 1;
int length2 = 1;
// 两个指针移动到尾部
while (p1.next != null) {
p1 = p1.next;
length1++;
}
while (p2.next != null) {
p2 = p2.next;
length2++;
}
// 如果尾部不同, 则无交叉点
if (p1 != p2) return null;
// 将两个指针移动到头部
p1 = headA;
p2 = headB;
// 较长的指针先走一段
int diff = length1 - length2;
if (diff > 0) {
for (int i = 0; i < diff; i++) {
p1 = p1.next;
}
} else if (diff < 0) {
for (int i = diff; i < 0; i++) {
p2 = p2.next;
}
}
// 两个指针同时移动, 直到他们相遇
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
网友评论