文档章节

链表的中点,是否有环,有环时环的起点,环的长度,链表的长度

Lennie002
 Lennie002
发布于 2015/09/11 02:41
字数 372
阅读 131
收藏 9
  1.  查找链表的中点

LinkNode* middle(LinkNode* head)
{
     LinkNode *fast = head;       //快慢指针起点相同
     LinkNode *slow = head;
     
     //使用快慢指针
     while(fast && fast->next)
     {
          slow = slow->next;
          fast = fast->next->next;
     }
     
     if(fast)                  //根据结束条件  判断  中间节点的位置
             return slow;
     else  
             return slow->next;
      
}

2.  判断链表有环

bool isCircle(LinkNode* head)
{
     LinkNode *fast = head;
     LinkNode *slow = head;
     
     while(fast && fast->next)
     {
         slow = slow->next;
         fast = fast->next->next;
         
         if(slow == fast)  return true;
     }
     
     return false;
}

3.  计算环的起点, 链表长度, 还的环的长度

void  Circle(LinkNode * head)
{
    int slowStep;   //slow 走过的步数
    int pos;        //从链表开始记录的步数
    
    LinkNode *slow = head;
    LinkNode *fast = head;
    
    slowStep = 1;
    while(fast && fast->next)
    {
         slow = slow->next;
         fast = fast->next->next;
         
         slowStep++;
         if(slow == fast)  break;
    }
    
    pos = 1;
    LinkNode *p = head;
    while(p != slow)   //同时从第一个相交的点 和  起点开始遍历
    {
        p = p->next;
        slow = slow->next;
        
        pos++;
    }
    
    /*
       环的起点    p;
       链表的长度  slowStep+pos-1;
       环的长度    slowSteps; 
    */
     
     return;
    
}

//方法2 根据hash查找环的起点
LinkNode * CircleStart(LinkNode* head)
{
     unoedered_set<LinkNode*> hash;
     
     LinkNode* p = head;
     while(p)
     {
          if(hash.find(p) == hash.end())
          {
               hash.insert(p);
          }else
               break;
          p = p->next;
     }
     
     return p;
}
//方法2 计算环的长度
int CircleLength(LinkNode* head)
{
     LinkNode *fast = head;
     LinkNode *slow = head;
     
     while(fast && fast->next)
     {
         slow = slow->next;
         fast = fast->next->next;
         
         if(slow == fast)  break;
     }
     
     
     int lenght = 1;
     while(true)
     {
         slow = slow->next;
         fast = fast->next->next;
         length++;
         
         if(slow == fast)  break;  //再一次相遇时   slow 走了一圈,fast走了两圈。
     }
     
     return length;
     
}


© 著作权归作者所有

Lennie002
粉丝 8
博文 120
码字总数 64058
作品 0
大连
私信 提问
142. Linked List Cycle II

题目描述:给一个链表,判断其中环的起始结点,若没有环则返回null。要求不改变链表,空间复杂度O(1)。 分析:这题与141题是同一个算法引出的一系列问题,即Floyd判圈算法,又称龟兔赛跑算法...

Nautilus1
2017/11/13
0
0
链表中环的起点 Linked List Cycle II

问题: Given a linked list, return the node where the cycle begins. If there is no cycle, return . Note: Do not modify the linked list. Follow up: Can you solve it without using......

叶枫啦啦
2017/09/29
63
0
面试精选之链表问题集锦

链表问题是面试过程中经常被问到的一部分,很考查编程功底。最近刷了 LeetCode 上链表部分的面试题,我总结了一些有代表性的链表问题。 本文使用的是 Java 语言,下面是所用到的链表节点的定...

JohnnyShieh
2017/11/27
0
0
算法初级面试题03——打印链表公共部分、判断链表是否为回文、按值划分链表为小于等于大于、复制随机指针链表、两链表相交判断的一系列问题

接着前面的内容 这次主要讨论链表相关的题目 机试的时候怎么快怎么做,面试的时候要聊时间O(N),额外空间复杂度达到O(1)。 题目十 打印两个有序链表的公共部分 【题目】 给定两个有序链表的头...

kent鹏
01/17
0
0
LeetCode 142. Linked List Cycle II (链表环起点)

Given a linked list, return the node where the cycle begins. If there is no cycle, return . To represent a cycle in the given linked list, we use an integer which represents the......

dby_freedom
2018/12/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部