整数转换 webserver mfc performance encryption neo4j triggers flexbox insert Avalon formvalidator.js bootstrap后台模板 直销系统源码 jq解析json jq获取元素宽度 一兆等于多少字节 idea整理代码 js原生点击事件 mysql 导入数据 python集合 python创建txt文件并写入 python例子 python怎么下载 python获取时间戳 java集成 java中的数据类型 java数组扩容 java实例方法 java实现栈 java安装 java开发语言 php实例 pascal教程 街头篮球辅助 图解设计模式 圆形截图 免费书籍 视频相册制作软件 用流量打电话的软件 页面刷新
当前位置: 首页 > 学习教程  > 编程语言

思维私塾——快慢指针

2020/12/5 10:44:18 文章标签:

在一些常见的算法题目中,尤其是链表题目中,在解法中常常会看到快慢指针的使用。 快慢指针正如其名,使用一快一慢两个指针,对链表进行遍历。主要是利用两个指针的速度差; 两倍速:用于求中间指针或者循环链…

在一些常见的算法题目中,尤其是链表题目中,在解法中常常会看到快慢指针的使用。

快慢指针正如其名,使用一快一慢两个指针,对链表进行遍历。主要是利用两个指针的速度差;

  • 两倍速:用于求中间指针或者循环链表
  • 恒定n个差值:用于寻找倒数第N个指针

下面我们就来看几道快慢指针的实际应用

环形链表

理论基础很简单,利用一块一慢两个指针遍历链表,如果链表存在环,那么快指针一定能套圈慢指针,所以只需要判断快指针能否追上慢指针,追上说明有环,未追上则说明没有环。

 public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow=head;
        ListNode fast = head.next;
        while(slow!=fast){
            if(fast==null||fast.next==null){
                return false;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }

找中间值

我们把一个链表看成一个跑道,快指针的速度是慢指针速度的两倍,那么当快指针跑完时,慢指针正好跑到一半,一次达到找中间节点的目的。

public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

删除倒数第N个节点

快指针先走n步,慢指针开始和快指针同步移动到next,当快指针到达链表尾部时,慢指针刚好移动到倒数第n-1个节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode fast = head;
    ListNode slow = head;
    //慢指针比快指针慢N步,那么快指针指向末尾的null时,慢指针刚好指向要删除结点的前驱结点
    while (fast.next != null) {
        fast = fast.next;
        if (n == 0) {
            slow = slow.next;
        } else {
            n--;
        }
    }
    if (n != 0) { //没追上,说明删除的是头指针
        return head.next;
    } else {
        slow.next = slow.next.next;
    }
    return head;

}

总结

快慢指针主要是利用一快一慢的特性来解决诸如:环形链表、中间值、删除倒数第N个节点的问题,另外在链表迭代中,时间复杂度是O(n)的量级,是一种能有效控制时间复杂度的算法。

最后

  • 如果觉得看完有收获,希望能给我点个赞,这将会是我更新的最大动力,感谢各位的支持
  • 欢迎各位关注我的公众号【java冢狐】,专注于java和计算机基础知识,保证让你看完有所收获,不信你打我
  • 如果看完有不同的意见或者建议,欢迎多多评论一起交流。感谢各位的支持以及厚爱。

image


本文链接: http://www.dtmao.cc/news_show_450304.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?