快慢指针实现不依赖计数器寻找中位数(linked list)

时间:2022-06-07 11:52:58
该方法在不借助计数器变量实现寻找中位数的功能。原理是:快指针的移动速度是慢指针移动速度的2倍,因此当快指针到达链表尾时,慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素,当快指针移动x次后到达表尾(1+2x),说明链表有奇数个结点,直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时可以根据“规则”返回上中位数或下中位数或(上中位数+下中位数)的一半。
while (fast&&slow) 
  { 
  if (fast->next==NULL) 
  return slow ->data; 
  else if (fast->next!= NULL && fast->next->next== NULL) 
  return (slow ->data + slow ->next->data)/2; 
  else 
  { 
  fast= fast->next; 
  fast= fast->next; 
  slow = slow ->next; 
  } 
  }

快慢指针实现不依赖计数器寻找中位数(linked list)的更多相关文章

  1. Faster\Slower 快慢指针的应用

    leetcode很多题目都是利用快慢指针来解决题目,下面具体讲解下快慢指针. 概念: 快指针在每一步走的步长要比慢指针一步走的步长要多.快指针通常的步速是慢指针的2倍.在循环中的指针移动通常为:fas ...

  2. java数据结构面试问题—快慢指针问题

    上次我们学习了环形链表的数据结构,那么接下来我们来一起看看下面的问题, 判断一个单向链表是否是环形链表? 看到这个问题,有人就提出了进行遍历链表,记住第一元素,当我们遍历后元素再次出现则是说明是环形链 ...

  3. c 链表之 快慢指针 查找循环节点

    参考:http://blog.csdn.net/wenqian1991/article/details/17452715 上面分析了 根据这张图 推倒出 数学公式. 刚接触 不能一下弄明白.下面结合上 ...

  4. LeetCode OJ 143. Reorder List(两种方法,快慢指针,堆栈)

    Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do thi ...

  5. 【算法分析】如何理解快慢指针?判断linked list中是否有环、找到环的起始节点位置。以Leetcode 141. Linked List Cycle, 142. Linked List Cycle II 为例Python实现

    引入 快慢指针经常用于链表(linked list)中环(Cycle)相关的问题.LeetCode中对应题目分别是: 141. Linked List Cycle 判断linked list中是否有环 ...

  6. Who's in the Middle - poj 2388 (快速排序寻找中位数)

    题意; 寻找中位数 利用快速排序来寻找中位数. #include <iostream> using namespace std; int N; ]; int Median(int left ...

  7. &lbrack;LeetCode&rsqb; Remove Nth Node From End of List 快慢指针

    Given a linked list, remove the nth node from the end of list and return its head. For example, Give ...

  8. reorder-list——链表、快慢指针、逆转链表、链表合并

    Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do thi ...

  9. c 链表之 快慢指针 查找循环节点(转)

    上面分析了 根据这张图 推倒出 数学公式. 刚接触 不能一下弄明白.下面结合上面文章的分析.仔细推倒一下 , 一般设置 快指针 速度是 慢指针的2倍.及 快指针每次遍历两个指针, 慢指针每次遍历1个指 ...

随机推荐

  1. 关于UIView需要看的一些官方文档

    View Controller PG(Programming Guide)  看过一遍 View PG 正在看 Drawing and Printing PG Quartz 2D PG 更高级的cus ...

  2. jquery 几点注意事项

    jquery触发hover事件 使用 mouseenter/mouseleave/mouseover/mouseout

  3. java学习之IO文件分割

    package om.gh.homework; import java.io.*; /** * 实现分割文件; * @param file */ public class HomeWork { /** ...

  4. Memcache服务搭建

    Memcache Memcache的作用网上资料都讲的很好,说简单点就是减轻读取数据库的压力,原理也很简单: 被请求的数据会先到memcache里去取,如果没有就去数据库里取,顺便给memcache带 ...

  5. html或者jsp页面刷新问题

    setTimeout(function(){window.location.reload();//刷新当前页面.},2000) window.location.reload();//刷新当前页面.pa ...

  6. Java 并发编程-再谈 AbstractQueuedSynchronizer 2&colon;共享模式与基于 Condition 的等待 &sol; 通知机制实现

    共享模式acquire实现流程 上文我们讲解了AbstractQueuedSynchronizer独占模式的acquire实现流程,本文趁热打铁继续看一下AbstractQueuedSynchroni ...

  7. Java捕获异常的问题

    ---恢复内容开始--- 在Java编译过程中,有时候会出现输入未按照规定输入的情况,此时需要警告用户输入错误,这就会是程序运行过程中出现异常.异常就是可预测但是又没办法消除的一种错误.所以在编写过程 ...

  8. MFC中处理UI界面时的注意点

    最近开发时,在处理界面上遇到了下面的问题: 上位机与下位机通信时,如果出现超时,弹出MessageBox提示的情况下,更新界面上的CStatic控件会出现重影. 经过调查发现 原因是由于在UI线程中处 ...

  9. HTML5 canvas 学习

    一.canvas简介 ​ <canvas> 是 HTML5 新增的,一个可以使用脚本(通常为JavaScript)在其中绘制图像的 HTML 元素.它可以用来制作照片集或者制作简单(也不是 ...

  10. torch&period;nn&period;CrossEntropyLoss

    class torch.nn.CrossEntropyLoss(weight=None, size_average=True, ignore_index=-100, reduce=True) 我这里没 ...