链表神操作 --- 快慢指针
快慢指针，顾名思义，就是操作链表的时候，使用两个指针，一快一慢。灵活使用快慢指针，可以巧妙的解决很多问题。本文将介绍如下问题：
- 找到链表中的倒数第K个节点(leetCode 剑指offer22)；
- 找到链表的中点；
- 删除链表倒数第K个节点；
- 判断链表是否有环
先定义一个链表类：
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。
一、找到链表的倒数第K个节点
1. 题目描述：
假如现有如下链表，且k = 2：
1 --> 2 --> 3 --> 4 --> 5 --> 6那么则应输出(倒数第K个节点，而不是倒数第K个节点的值)：
5 --> 62. 题目分析：
- 定义两个指针，一个
fast，一个slow，一开始都在第一个位置； - 假设链表长度为
n，倒数第k个，那么就是顺数第n-k+1个，需要移动的步数就是n-k； - 让
fast先走k步，此时fast离链表尾就还有n-k步； - 然后让
slow和fast同时向后移动，当fast移动到最后的时候，slow就移动了n-k步，就找到了目标节点。
3. 代码实现：
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for(int i=0; i<k; i++) {
fast = fast.next;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}二、找到链表的中点
1. 题目描述：
输入链表：
1 --> 2 --> 3 --> 4 --> 5 --> 6则应输出：
4 --> 5 --> 6输入：
1 --> 2 --> 3 --> 4 --> 5输出：
3 --> 4 --> 52. 题目分析：
- 定义两个指针，一个
fast，一个slow，一开始都在第一个位置； - 然后同时移动两个指针，让
fast比slow快一倍，当fast到尾了，slow就刚好在中点。
3. 代码实现：
public ListNode getMiddle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}三、删除链表倒数第K个节点
1. 题目描述：
输入如下链表，且k = 2：
1 --> 2 --> 3 --> 4 --> 5 --> 6输出：
1 --> 2 --> 3 --> 4 --> 62. 题目分析：
- 定义两个指针，一个
fast，一个slow，一开始都在第一个位置； - 要删除倒数第
k个节点，就要找到它的前一个节点，即倒数第k+1个节点，顺数就是(n-k-1)； - 所以让
fast快k+1步，等fast到尾的时候，slow就在(n-k-1)的位置。
3. 代码实现：
public ListNode delFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
// 让fast比slow快k步
for(int i=0; i<k+1; i++) {
fast = fast.next;
}
// 将slow移到倒数k+1位置，经过该步骤，slow指向要删除节点的前一个节点
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
// 这里让前一个节点的next等于要删除节点的next，就将要删除的节点删除了
slow.next = slow.next.next;
return head;
}四、判断链表是否有环
1. 题目描述：
如果输入的是环形链表，则输出true，反之输出false。
2. 题目分析：
两个人在环形跑道上跑步，从同一起点出发，一个人速度快，一个人速度慢，不管他们的速度相差多少，只要是有速度差，他们总有再次相遇的时刻。所以，我们可以使用快慢指针，判断链表是否有环。如果两个指针会再次相遇，就是有环，反之无。
3. 代码实现：
public boolean hasCircle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}怎么样，关于快慢指针，大家学废了吗
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录