软件测试工程师 WebService 分库查询 npm安装 awk service fonts lua combobox x86 jaxb vue传值 bootstrap管理模板 ppt视频教程下载 jquery去掉空格 jquery事件绑定 python程序界面 matlab注释一段 java多行注释 mser算法 linux获取当前时间 maven插件 matlab取绝对值 matlab自然对数 idea格式化代码设置 oracle数据库创建表空间 hbuilder插件 docker创建容器 python怎么入门 java接口实现 java8时间 java替换字符串 java原始数据类型 javastringbuilder linux下载安装 linux如何安装 flash实例教程 机械下载 梦幻西游手游助手 raid0教程
当前位置: 首页 > 学习教程  > 编程语言

京东Java后端开发面试算法题(实习)

2020/9/19 15:44:10 文章标签:

京东Java后端开发面试算法题(实习)

1.给定一个链表,判断链表是否有环

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //方法一:双指针
    // public boolean hasCycle(ListNode head) {
    //     if(head==null||head.next==null){
    //         return false;
    //     }
    //     ListNode slow = head;
    //     ListNode fast = head.next;
    //     while(slow!=fast){
    //         if(fast==null||fast.next==null){
    //             return false;
    //         }
    //         slow = slow.next;
    //         fast = fast.next.next;
    //     }
    //     return true;
    // }
    //方法二:哈希表
    public boolean hasCycle(ListNode head){
        Set<ListNode> nodesSeen = new HashSet<>();
        while (head != null) {
            if (nodesSeen.contains(head)) {
                return true;
            } else {
                nodesSeen.add(head);
            }
            head = head.next;
        }
        return false;

    }
}

2.环形链表II
返回链表开始入环的第一个节点

public class Solution {
    // public ListNode detectCycle(ListNode head) {
    //     Set<ListNode> visted = new HashSet<ListNode>();
    //     ListNode node = head;
        
    //     while(node!=null){
    //         if(visted.contains(node)){
    //             return node;
    //         }
    //         visted.add(node);
    //         node = node.next;
    //     }
    //     return null;
    // }
    //https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
    //双指针解决思路
    public ListNode detectCycle(ListNode head){
        ListNode fast = head,slow = head;
        while(true){
            if(fast==null||fast.next==null)
                return null;
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow)
                break;
        }
        fast = head;
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}

本文链接: http://www.dtmao.cc/news_show_200308.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?