单链表判断是否有环和环起始节点

面试的滴滴研究院暑期实习生,岗位机器学习,二面除了电话面还要视频面试写代码,两个问题:

  • 单链表判断是否有环以及找出环开始的节点
  • 建立二叉排序树并进行中序遍历

因为第二个之前有写过,所以没什么问题的过了;第一个其实也不难,但是有点紧张,最后面试官告诉我判断是否有环的函数写错了,哎。。。特此重新写下,mark之

package acmcoder;

class Node_t{
    int value;
    Node_t next;
    public Node_t(int value, Node_t next) {
        this.value = value;
        this.next = next;
    }
    public Node_t() {
        value = -999;
        next = null;
    }

    @Override
    public String toString() {
        return "Node_t: value=" + value;
    }


}

public class Test_didi {
    private boolean hasLoop(Node_t head){
        //使用快慢指针
        Node_t p = head.next;
        Node_t q = head.next;
        boolean res = false;
        while(q != null && q.next != null){
            p = p.next; 
            q = q.next.next;
            if(p == q){
                res = true;
                break;
            }
        }
        return res;
    }

    private Node_t crashNode(Node_t head){
        //假定一定有环
        //使用快慢指针
        Node_t p = head.next;
        Node_t q = head.next;
        while(q.next != null){
            p = p.next;
            q = q.next.next;
            if(p == q){
                break;
            }
        }
        return p;
    }

    private Node_t findCircleStartNode(Node_t head){
        boolean hasCircle = hasLoop(head);
        if(!hasCircle){
            return new Node_t();
        }else{
            //碰撞点到连接点的距离等于头指针到连接点的距离
            Node_t crash = crashNode(head);
            Node_t start = head.next;
            while(start != crash){
                start = start.next;
                crash = crash.next;
            }
            return crash;
        }
    }

    private int circleLen(Node_t head){
        //找到碰撞点之后从碰撞点出发然后再次碰撞
        Node_t crash = crashNode(head);
        Node_t p = crash;
        Node_t q = crash;
        int len = 0;
        while(q.next != null){
            p = p.next;
            q = q.next.next;
            len++;
            if(p == q){
                break;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        //建立单链表
        Node_t node1 = new Node_t(1, null);
        Node_t node2 = new Node_t(2, null);
        Node_t node3 = new Node_t(3, null);
        Node_t node4 = new Node_t(4, null);
        Node_t node5 = new Node_t(5, null);
        Node_t node6 = new Node_t(6, null);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node4;
        //判断是否有环
        Test_didi test = new Test_didi();
        boolean hs = test.hasLoop(node1);
        System.out.println("Has circle: " + hs);
        //找出环的起点
        Node_t circleStart = test.findCircleStartNode(node1);
        System.out.println("Circle starts: " + circleStart.toString());
        //计算环的长度
        int len = test.circleLen(node1);
        System.out.println("Circle length: " + len);

    }

}

虽然面的不好, 好在还是拿到了offer, 侥幸

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:类型转换

正文之前 学习,不如爆文?反正晚上也不会学习,某个家伙也对我爱理不理的!!!!(这才是最骚的吧),刚好欠了 C++ Primer太多烂账了。不如赶紧还了! 对了...

2958
来自专栏desperate633

LintCode 排列序号题目分析代码

给出一个不含重复数字的排列,求这些数字的所有排列按字典序排序后该排列的编号。其中,编号从1开始。 样例 例如,排列 [1,2,4]是第 1个排列。

813
来自专栏前端正义联盟

我来重新学习 javascript 的面向对象(part 5)

这是最后的最后了,我会顺便总结一下各种继承方式的学习和理解。(老板要求什么的,管他呢)

761
来自专栏Android知识点总结

再见kotlin----01语句控制

672
来自专栏大数据杂谈

从 Zero 到 Hero ,一文掌握 Python

1709
来自专栏用户画像

迷语博士的难题

两面族是荒岛上的一个新民族,他们的特点是说话真一句假一句且真假交替。如果第一句为真,则第二句是假的;如果第一句为假的,则第二句就是真的,但是第一句是真是假没有规...

681
来自专栏cmazxiaoma的架构师之路

Java小白必须会的一道面试算法题

4263
来自专栏斑斓

编程修炼 | Scala中Stream的应用场景及其实现原理

假设一个场景需要在50个随机数中找到前两个可以被3整除的数字。听起来很简单,我们可以这样来写: def randomList = (1 to 50).map(_...

2835
来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

1928
来自专栏恰同学骚年

剑指Offer面试题:9.二进制中1的个数

  一个基本的思路:先判断整数二进制表示中最右边一位是不是1。接着把输入的整数右移一位,此时原来处于从右边数起的第二位被移到最右边了,再判断是不是1。这样每次移...

662

扫码关注云+社区