链表骚操作 --- 快慢指针

原创
10/18 18:05
阅读数 39

快慢指针,顾名思义,就是操作链表的时候,使用两个指针,一快一慢。灵活使用快慢指针,可以巧妙的解决很多问题。本文将介绍如下问题:

  • 找到链表中的倒数第K个节点(leetCode 剑指offer22);
  • 找到链表的中点;
  • 删除链表倒数第K个节点;
  • 判断链表是否有环

先定义一个链表类:

public class ListNode {
 int val;
 ListNode next;
 ListNode(int x) {
  val = x;
 }
}

一、找到链表的倒数第K个节点

1. 题目描述:

假如现有如下链表,且k = 2

1 --> 2 --> 3 --> 4 --> 5 --> 6

那么则应输出(倒数第K个节点,而不是倒数第K个节点的值):

5 --> 6

2. 题目分析:

  • 定义两个指针,一个 fast,一个 slow,一开始都在第一个位置;
  • 假设链表长度为 n,倒数第 k个,那么就是顺数第 n-k+1个,需要移动的步数就是 n-k
  • fast先走 k步,此时 fast离链表尾就还有 n-k步;
  • 然后让 slowfast同时向后移动,当 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 --> 5

2. 题目分析:

  • 定义两个指针,一个 fast,一个 slow,一开始都在第一个位置;
  • 然后同时移动两个指针,让 fastslow快一倍,当 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 --> 6

2. 题目分析:

  • 定义两个指针,一个 fast,一个 slow,一开始都在第一个位置;
  • 要删除倒数第 k个节点,就要找到它的前一个节点,即倒数第 k+1个节点,顺数就是 (n-k-1)
  • 所以让 fastk+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;
}

怎么样,关于快慢指针,大家学废了吗



-java开发那些事-
长按扫描二维码
关注我 获取更多内容


本文分享自微信公众号 - java开发那些事(javawebkf)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部