请用简单的例子说明快慢指针的差别
时间: 2023-05-31 22:06:02 浏览: 54
假设有一个单向链表,其中包含一些节点,每个节点都有一个值和一个指向下一个节点的指针。
使用快慢指针可以解决以下问题:
1. 判断链表是否有环
快慢指针从同一个起点开始遍历链表,快指针每次移动两个节点,慢指针每次移动一个节点。如果链表有环,那么快指针最终一定会追上慢指针,因为快指针每次移动两个节点,慢指针每次移动一个节点,所以快指针会在某个时刻“跨过”慢指针,这样两个指针之间的距离就会缩短1个节点。如果链表没有环,那么快指针最终会到达链表的末尾,此时慢指针也会到达链表的末尾。
2. 找到链表的中间节点
快慢指针从同一个起点开始遍历链表,快指针每次移动两个节点,慢指针每次移动一个节点。当快指针到达链表的末尾时,慢指针到达的节点就是链表的中间节点。如果链表的节点数是偶数,则中间节点是中间两个节点中的任意一个。
举个例子,假设链表的节点值依次为1、2、3、4、5、6、7,使用快慢指针可以得到以下结果:
- 判断链表是否有环:快指针和慢指针在节点5处相遇,说明链表有环。
- 找到链表的中间节点:快指针到达节点7时,慢指针到达节点4,所以链表的中间节点是节点4。
相关问题
用java代码实现快慢指针
以下是使用Java代码实现快慢指针的示例:
```
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
```
在这个示例中,我们定义了一个链表节点`ListNode`类,包含一个值和一个指向下一个节点的指针。然后我们定义了一个`middleNode`方法,用于找到链表的中间节点。
在方法中,我们定义了两个指针`slow`和`fast`,初始值都指向链表头节点`head`。然后我们通过一个`while`循环,每次将`slow`指针向后移动一步,将`fast`指针向后移动两步,直到`fast`指针到达链表末尾或者倒数第二个节点。此时,`slow`指针就指向链表的中间节点。
这就是一个简单的使用Java代码实现快慢指针的示例。
用java实现快慢指针算法
以下是用Java实现快慢指针算法的示例代码:
```
public ListNode middleNode(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
```
其中,`ListNode`是链表节点的定义,包含一个`val`属性和一个指向下一个节点的`next`指针。在这个示例中,我们使用两个指针`fast`和`slow`,分别从链表头部遍历链表,一个每次走一个节点,一个每次走两个节点。当快指针走到链表末尾时,慢指针所在的位置就是链表的中间节点。
需要注意的是,在遍历链表时,我们需要保证`fast`指针不为空并且`fast.next`指针也不为空,否则会出现空指针异常。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)