【腾讯】环形链表(证明环的位置)

简介: 【腾讯】环形链表(证明环的位置)

1. 题目描述

题目链接:环形链表II

2. 题目分析

  1. 题目在上一个环形链表上让你证明有环无环,进而让你求此环点
  2. 首先,我们想想,在上一题中,我们快指针走2步,慢指针走一步,也就是
  • 快指针 = 2 * 慢指针
  • 快指针比慢指针多走了nb,最后交汇在环中的某一点
  • 由上述式子相减
  • 慢指针走的步数 = nb
  • 所以,我们考虑考虑,我们怎么才能让慢指针走到环点呢?
  • 慢指针走a+nb时,是不是就走到环点了
  • 所以,我们只需要再让慢指针走a步,也就是从头再定义一个指针,当两指针相交时,此节点就是该环点
  1. 或者利用Map大法,第一个重复的结点就是环点(不过,大概率不能过面试)

3. 题目代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
       if(head == null){
           return null;
       }
       boolean f = false;
       ListNode p1 = head;
       ListNode p2 = head;
       while(p2.next != null && p2.next.next != null){
           p1 = p1.next;
           p2 = p2.next.next;
           if(p1 == p2){
               f = true;
               break;
           }
       }
       if(f){
           ListNode p3 = head;
           while(p3 != p1){
               p3 = p3.next;
               p1 = p1.next;
           }
           return p1;
       }else{
           return null;
       }
    }
}


目录
打赏
0
0
0
0
63
分享
相关文章
|
8月前
|
环形数组链表(java)
环形数组链表(java)
|
4月前
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
41 0
|
7月前
【数据结构OJ题】环形链表
力扣题目——环形链表
56 3
【数据结构OJ题】环形链表
|
7月前
【数据结构OJ题】环形链表II
力扣题目——环形链表II
50 1
【数据结构OJ题】环形链表II
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
76 2
|
7月前
|
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
47 0
|
9月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
93 1
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
64 1
|
8月前
|
单向环形链表-约瑟夫问题(java)
单向环形链表-约瑟夫问题(java)
【数据结构与算法 刷题系列】环形链表的约瑟夫问题
【数据结构与算法 刷题系列】环形链表的约瑟夫问题
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等