专栏首页JavaEE链表神操作 --- 快慢指针

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

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

  • 找到链表中的倒数第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 --> 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;
}

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 约瑟夫问题

    1、约瑟夫问题原题: n个小孩子手拉手围成一个圈,编号为k(1 <= k <= n )的人从1开始报数,报到m的那个人出列,它的下一位又从1开始报数,报到m的...

    贪挽懒月
  • 白话分布式系统

    1、单体应用介绍: 所谓单体应用,就是一些小型的应用,一个系统就是eclipse中的一个工程,然后打一个jar包或者war运行,这个jar包或者war就是整个...

    贪挽懒月
  • 排序算法 --- 计数排序

    前面说的那些排序算法,都是要通过比较来实现的。排序还能不通过比较来实现?是的,计数排序就是这么神奇。

    贪挽懒月
  • 程序员面试金典 - 面试题 02.08. 环路检测(快慢指针)

    给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。

    Michael阿明
  • Leetcode: Linked List Cycle II

    题目: Given a linked list, return the node where the cycle begins. If there is n...

    卡尔曼和玻尔兹曼谁曼
  • 腾讯云公布5G产品矩阵,年底前交付300个边缘计算中心

    8月25日,腾讯云率先公布5G新基建最新进展,成为国内首家全面构筑起覆盖“云-边-网-端”完整5G产品矩阵的云厂商。腾讯云网络总经理王亚晨透露,预计在今年底,腾...

    边缘计算
  • 切勿以偏概全 云计算SaaS层应用深度剖析

    云计算作为当前非常热门的技术话题之一,被越来越多的人所提及到,我们深究云计算应用的一些深层次的技术就不难发现,现在的云计算用户已经把中心逐渐放在了SaaS层面。...

    静一
  • python web开发环境搭建-web HelloWorld

      我的环境是:wamp1.7.4+python-2.5.2.+ mod_python-3.3.1.win32-py2.5-Apache2.2

    the5fire
  • 10行代码实现目标检测 |视觉进阶

    在本文中,我将向你展示如何使用Python在不到10行代码中创建自己的目标检测程序。

    朱晓霞
  • 牛!何恺明包揽2项ICCV 2017最佳论文奖!这位高考状元告诉你什么是开挂的人生

    大神终究是大神! 刚刚,AI 科技大本营获悉,继两次荣获 CVPR 最佳论文奖之后,何恺明参与的两篇最新论文又分别摘下 ICCV 2017 的最佳论文奖(Bes...

    AI科技大本营

扫码关注云+社区

领取腾讯云代金券