• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

链表骚操作 — 快慢指针

互联网 diligentman 1周前 (10-18) 7次浏览

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

  • 找到链表中的倒数第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步;
  • 然后让
    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 --> 5

2. 题目分析:

  • 定义两个指针,一个
    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 --> 6

2. 题目分析:

  • 定义两个指针,一个
    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;
}

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

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





java开发那些事-



长按扫描二维码

关注我 获取更多内容

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


喜欢 (0)