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

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

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

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

相关文章

来自专栏大数据和云计算技术

#算法基础#选择和插入排序

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第二篇《选择和插入排序》,非常赞!希望对大家有帮助,大家会喜欢! 系列文章: 由快速排序到分治思想 ...

3296
来自专栏数据结构与算法

树链剖分详解

前言 树链剖分是什么? 树链剖分,说白了就是一种让你代码不得不强行增加1k的数据结构-dms 个人理解:+1:joy: 有什么用? 证明出题人非常毒瘤 ...

2687
来自专栏zingpLiu

常用七种排序的python实现

算法复杂度分为时间复杂度和空间复杂度。其中, 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。

694
来自专栏菜鸟前端工程师

JavaScript学习笔记021-常用排序算法

382
来自专栏陈树义

如何检测链表中存在的环

链表有环的定义是,链表的尾节点指向了链接中间的某个节点。比如下图,如果单链表有环,则在遍历时,在通过结点J之后,会重新回到结点D。 ? 看了上面的定义之后,如...

2626
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-下

5、堆排序(HeapSort) 在接触“堆排序”前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了“完全二叉树”有一些重要的数学特性: ? 上图就是一...

1775
来自专栏有趣的Python

算法与数据结构(四)堆排序:优先队列实现

堆排序 排序次要的,接触新的数据结构;堆 堆和优先队列 Heap and Priority Queue 什么是优先队列? 普通队列:先进先出;后进后出 优先队...

3345
来自专栏枕边书

PHP实现堆排序

经验 工作了,面试我工作这家公司时被技术面打击得不行,因为自己的数据结构等基础学得实在太差,虽然原来是想做设计师的说。。。不过看在PHP写得还凑合的份上能来实习...

1687
来自专栏数据结构与算法

HihoCoder#1513 : 小Hi的烦恼(五维数点 bitset 分块)

五位数点问题,写个cdq分治套cdq分治套cdq分治套cdq分析就完了 可以用bitset搞

391
来自专栏ml

排序

排序法 平均时间 最差情形 稳定度 额外空间 冒泡 O(n2)     O(n2) 稳定 O(1) 交换     O(n2)     O(n2) ...

3065

扫码关注云+社区