面试题快慢链表和快慢指针

腾讯的一道面试题：如何快速找到位置长度单链表的中间节点？普通方法，就是先遍历，在从头找到2/length的中间节点。算法复杂度是：O(3*n/2)。而更快的方法就是利用快慢指针的原理。

快慢链表：利用标尺的思想，设置两个指针（一快一慢）*serach和*mid，刚开始都指向单链表的头结点。但是*search指针的移动速度是*mid的两倍。当*search到尾结点的时候，mid刚好到了中间。算法复杂度是：O(n/2)

int GetMidNode(LinkList *L,int elem){
  LinkList *search,*mid;
  mid = search = L; //指向头结点
  while (search->next != NULL){ //当存在下个结点的时候
    if (search->next->next!=NULL) {//检查下个的下个节点是否为空
      search = search->next->next;
      mid = mid->next;
    }
    else
      search = search->next;
  }
  elem = mid->data;
  return elem;
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • C++面试题之结构体内存对齐计算问题总结大全

    C++面试题之结构体内存对齐计算问题总结大全

    前言 本文给大家介绍的是关于C++结构体内存对齐计算的相关内容,内存对齐计算可谓是笔试题的必考题,但是如何按照计算原则算出正确答案一开始也不是很容易的事,所以专门通过例子来复习下关于结构体内存对齐的计算问题.话不多说,来一起看看详细介绍吧. 编译环境:vs2015 对齐原则: 原则1:数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在offset为0的地方,以后每个数据成员的对齐按照#pragma pack指定的数值和这个数据成员自身长度中,比较小的那个

  • C++ 面试题翻译电话号码实例代码

    C++ 面试题翻译电话号码实例代码

    C++ 面试题翻译电话号码实例代码 例如: 输入:OneTwoThree 输出:123 输入:OneTwoDoubleTwo 输出:1222 输入:1Two2 输出:ERROR 输入:DoubleDoubleTwo 输出:ERROR 有空格,非法字符,两个Double相连,Double位于最后一个单词 都错误. #include <iostream> #include <string> using namespace std; void process(string str) {

  • Java高级面试题小结

    这是一个高级Java面试系列题中的第一部分.这一部分论述了可变参数,断言,垃圾回收,初始化器,令牌化,日期,日历等等Java核心问题.接下来我们就看看具体都有哪些问题. 1.什么是可变参数? 2.断言的用途? 3.什么时候使用断言? 4.什么是垃圾回收? 5.用一个例子解释垃圾回收? 6.什么时候运行垃圾回收? 7.垃圾回收的最佳做法? 8.什么是初始化数据块? 9.什么是静态初始化器? 10.什么是实例初始化块? 11.什么是正则表达式? 12.什么是令牌化? 13.给出令牌化的例子? 14.

  • 亚马逊经典面试题实例详解

    亚马逊面试题: 如下所示的Map中,0代表海水,1代表岛屿,其中每一个岛屿与其八领域的区间的小岛能相连组成岛屿群.写代码,统计Map中岛屿个数. /* Q1. Map [ 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 ] */ 实现代码: #include<iostream> #include<queue> using namespace

  • Java main 方法面试题的详细整理

    Java main 方法面试题的详细整理 1.不用main方法如何定义一个类? 不行,没有main方法我们不能运行Java类. 在java 7之前,你可以通过使用静态初始化运行Java类.但是,从Java 7开始就行不通了. 2.main()方法需要的参数不是字符串数组? 不是的,main()方法的参数必须是字符串数组. 但是,在引进变参时,你可以将字符串类型的变参作为参数传递给main()方法.变参一定得是数组. package com.instanceofjava; public class

  • 分享几道你可能遇到的python面试题

    本文主要给大家介绍的是关于最近在面试中遇到的几个python面试题,分享出来供大家参考学习,下面话不多说,来一起看看详细的介绍: 一.生成斐波那契数列并取前10项 def func(m): n,a,b = 0,1,1 while n < m: yield a a,b = b,a+b n += 1 for one in func(10): print one 这个可以说是一道常见的简单算法题了,关键点就是理解a,b=b,a+b以及yield的作用. 二.扩展一个列表,列表中的元素可能也包含列表 d

  • Java常见数据结构面试题（带答案）

    1.栈和队列的共同特点是(只允许在端点处插入和删除元素) 4.栈通常采用的两种存储结构是(线性存储结构和链表存储结构) 5.下列关于栈的叙述正确的是(D)      A.栈是非线性结构B.栈是一种树状结构C.栈具有先进先出的特征D.栈有后进先出的特征 6.链表不具有的特点是(B)A.不必事先估计存储空间       B.可随机访问任一元素 C.插入删除不需要移动元素      D.所需空间与线性表长度成正比 7.用链表表示线性表的优点是(便于插入和删除操作) 8.在单链表中,增加头结点的目的是(

  • 面试题快慢链表和快慢指针

    腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到2/length的中间节点.算法复杂度是:O(3*n/2).而更快的方法就是利用快慢指针的原理. 快慢链表:利用标尺的思想,设置两个指针(一快一慢)*serach和*mid,刚开始都指向单链表的头结点.但是*search指针的移动速度是*mid的两倍.当*search到尾结点的时候,mid刚好到了中间.算法复杂度是:O(n/2) int GetMidNode(LinkList *L,int elem){ Li

  • Java 八道经典面试题之链表题

    Java 八道经典面试题之链表题

    目录 第一题 移除链表元素 第二题 反转链表 第三题 链表的中心结点 第四题 倒数第k个结点 第五题 合并两个有序链表 第六题 链表分割 第七题 判断是否回文 第八题 相交链表 第一题 移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 . 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 这道题还是比较简单的我们需要让删除的节点的前一个结点指向删

  • 给定链表中间节点指针，删除中间节点的方法

    问题如下输入:链表 a->b->c->d->e中指向节点c的指针输出:无返回值,但新链表变为a->b->d->e解答:想了好久没想出来,看了提示才知道解法的.这里用到了一个小技巧.要删除中间节点,但是我们不知道要删除节点的上一个节点p,所以无法通过修改指针的方法(p->next=del->next)来删除节点,但知道要删除节点的后一个节点,那么我们换一个思路,把要删除的节点的数据与该节点的后一个节点的数据交换,然后删除后一个节点,从而达到目的.但是该方

  • Java数据结构之单链表的实现与面试题汇总

    目录 1 单链表 1.1 单链表介绍 1.2 单链表的实现思路分析 1.3 实现代码 2 单链表的面试题 2.1 统计单链表中有效节点数量 2.2 新浪–倒数第k个节点 2.3 腾讯–单链表的反转 2.4 百度–逆序打印单链表 1 单链表 1.1 单链表介绍 由于顺序表的插入删除操作需要移动大量的元素,影响了运行效率,因此引入了线性表的链式存储——单链表.单链表通过一组任意的存储单元来存储线性表中的数据元素,不需要使用地址连续的存储单元,因此它 不要求在逻辑上相邻的两个元素在物理位置上也相邻.

  • C++实现LeetCode(138.拷贝带有随机指针的链表)

    C++实现LeetCode(138.拷贝带有随机指针的链表)

    [LeetCode] 138. Copy List with Random Pointer 拷贝带有随机指针的链表 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Example 1: Input: {"$id"

  • 详解C语言中二级指针与链表的应用

    详解C语言中二级指针与链表的应用

    目录 前言 二级指针讲解 链表的应用 定义双链表的结构体 创建双链表 前言 这篇文章即将解决你看不懂或者不会写链表的基本操作的问题,对于初学者而言,有很多地方肯定是费解的.比如函数的参数列表的多样化,动态分配内存空间函数malloc等,其实这些知识和指针联系紧密,尤其是二级指针.那么开始好好的学习这篇文章吧! 二级指针讲解 简述:其实就是一个指针指向另一个指针的地址. 我们都知道指针指向地址,但是指针自身也是一个变量,当然也可以被二级指针所指向. 语法:形如 int x = 10; int *q

  • C语言常见的指针笔试题解析

    目录 笔试题1 笔试题2 笔试题3 笔试题4 笔试题5 笔试题6 笔试题7 笔试题8 在我们学习指针之后,应该在实际应用中去理解和掌握它,毕竟实践才是检验真理的唯一标准,我们以后在找工作的过程中免不了会遇到与指针相关的试题,本篇文章可以帮助我们提前了解一些常见的指针考点.在学习这篇文章之前可以根据需要对指针进行简要复习. 注:本篇文章所有代码均在X86环境下运行. 笔试题1 #include <stdio.h> int main() { int a[5] = { 1,2,3,4,5 }; in

  • C语言深入讲解链表的使用

    C语言深入讲解链表的使用

    目录 一.链表的概念 二.链表的分类 1. 单向或者双向链表 2. 带头或者不带头(是否有自带哨兵位头结点) 3. 循环或者非循环链表 4. 无头单向非循环链表和带头双向循环链表 3.链表的实现(代码和注释) 4.链表oj题(小试牛刀) 总结 现实生活中的火车就像一个完整的链表,现在我们来深入理解一下链表这个数据结构. 一.链表的概念 概念:链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 . 注: 1.从上图中可看出,链式结构在逻辑上是连续

  • java实现单链表中是否有环的方法详解

    这是一道微软经典笔试题,就是两个指针h1,h2都从头开始遍历单链表,h1每次向前走1步,h2每次向前走2步,如果h2碰到了NULL,说明环不存在:如果h2碰到本应在身后的h1说明环存在(也就是发生了套圈). 如果环不存在,一定是h2先碰到NULL: 如果环存在,h2与h1一定会相遇,而且相遇的点在环内:h2比h1遍历的速度快,一定不会在开始的那段非环的链表部分相遇,所以当h1,h2都进入环后,h2每次移动都会使h2与h1之间在前进方向上的差距缩小1,最后,会使得h1和h2差距减少为0,也即相遇

  • JAVA--HashMap热门面试题

    1. 为什么我们建议在定义HashMap的时候,就指定它的初始化大小呢? 答:在当我们对HashMap初始化时,如果没有为其设置初始化容量,那么系统会默认创建一个容量为16的大小的集合.当我们向HashMap中添加元素时,如果HashMap的容量值超过了它的临界值(默认16*0.75=12)时,(0.75是HashMap的加载因子)HashMap将会重新扩容到下一个2的指数次幂(2^4=16 下一个2的指数次幂是2^5=32).由于HashMap扩容要进行resize的操作,频繁的resize,

随机推荐