专栏首页机器学习实践二三事单链表判断是否有环和环起始节点

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

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

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

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

相关文章

  • 微信老外产品经理:《中国移动应用设计趋势》

    编者按:本文作者 Dan Grover 是一名产品设计师、工程师和企业家,现在是腾讯微信项目的产品经理。2014年 底,他写过一篇《中国移动应用设计趋势》,引起...

    GavinZhou
  • NLP常用数据集

    原文地址: https://machinelearningmastery.com/datasets-natural-language-processing/ 针...

    GavinZhou
  • Inception-v4

    Google Research的Inception模型和Microsoft Research的Residual Net模型两大图像识别杀器结合效果如何?在这篇2...

    GavinZhou
  • (一)MessageQueue之消息入队

    比如我们在 16:10:40s 入队一个消息 A,41s入队的消息 B,42s 入队消息C

    木子杂志
  • 初级算法(2)-链表

    表的删除就是指针的移动,将待删除节点的指针移动到下一个节点 题1:删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。 虽然我们并不知道,这个节点...

    方丈的寺院
  • 腾讯与山水文园集团共建腾讯山水智慧试验区 | 数字文旅周报18期(6.24-6.30)

    ? 腾讯与山水文园集团 共建腾讯山水智慧试验区 6月24日,腾讯与山水文园集团就共同建设“腾讯山水智慧试验区”项目在京签署战略合作协议。 双方将依托山水文园集...

    腾讯文旅
  • 翻转链表 II

    一份执着✘
  • LeetCode - 反转链表

    原题地址:https://leetcode-cn.com/problems/reverse-linked-list/)

    晓痴
  • 【一天一大 lee】填充每个节点的下一个右侧节点指针 II (难度:中等) - Day20200928

    填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

    前端小书童
  • 【Leetcode】117. 填充每个节点的下一个右侧节点指针 II

    struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 nex...

    Leetcode名企之路

扫码关注云+社区

领取腾讯云代金券