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

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

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

因为第二个之前有写过,所以没什么问题的过了;第一个其实也不难,但是有点紧张,最后面试官告诉我判断是否有环的函数写错了,哎。。。特此重新写下,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 条评论
登录 后参与评论

相关文章

来自专栏AzMark

Python函数

1437
来自专栏个人随笔

Java 面向对象三大特征之一:封装

面向对象三大特征之一:封装 概念: 将类的某些信息隐藏在类内部,不允许外部程序直接访问,而是通过该类提供的方法类实现对隐藏信息的操作和访问 封装的好处: 隐藏...

3417
来自专栏轮子工厂

4. C语言 -- 一个由数据类型和取值范围引发的 BUG

之前看到有人留言催更,老夫的心里的竟然有一丝惊喜和兴奋。上周说要改版嘛( 。_ 。) ✎然后我就紧赶慢赶出了这篇稿子,但是由于一些原因,在今天才与大家间面。

632
来自专栏编程

关于python字典类型最疯狂的表达方式

[译]关于python字典类型最疯狂的表达方式 一个Python字典表达式谜题 这个子字典是从哪里来的 Umm..好吧,可以得到什么结论呢? 一篇来自 Dan ...

18610
来自专栏风口上的猪的文章

.NET面试题系列[3] - C# 基础知识(1)

重要程度:10/10,身家性命般重要。通常这也是各种招聘工作的第一个要求,即“熟悉C#”的一部分。连这部分都不清楚的人,可以说根本不知道自己每天都在干什么。我们...

712
来自专栏LinkedBear的个人空间

唠唠SE的面向对象-01——对象 原

每个对象都有自己独特的状态标识和行为对象的属性(attribute),或者状态(state)。

602
来自专栏JavaEE

Java面试题-01前言:面试题:总结:

1555
来自专栏进击的君君的前端之路

JavaScript面向对象编程指南 第一、二章知识点整理

1055
来自专栏大数据杂谈

从 Zero 到 Hero ,一文掌握 Python

1659
来自专栏鸿的学习笔记

Python和Scala的定义变量

每一门的编程语言背后都代表着某一种特别的哲学,由这一哲学进而设计出属于这门程序语言的语法,Python和Scala也不例外。我们从变量的定义去一窥Python和...

812

扫码关注云+社区