NC3链表中环的入口节点

链表中环的入口节点

https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425ad?tab=answerKey

- 1、题目描述：

图片说明
- 2、题目链接：
https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425ad?tpId=117&tqId=37713&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

-3、设计思想：
图片说明

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-5、代码：
c++版本:

 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
           if (head == nullptr) {
            return nullptr;
           }
         ListNode *slow = head;
         ListNode *fast = head;
         while(fast != NULL &amp;&amp; fast-&gt;next != NULL){
            fast = fast-&gt;next-&gt;next;//快指针移动两格
            slow = slow-&gt;next;//慢指针移动一格
            if(fast == slow){//当快慢指针相遇的时候，就让慢指针和head指针都移动一步，直到head和slow相遇就找到了入环节点
                while(head != slow){
                    slow = slow-&gt;next;
                    head = head-&gt;next;
                }
                return head;
            }
         }
         return NULL;

    }
};

Java版本：

/**
 * 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;
           }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null &amp;&amp; fast.next != null){
            fast = fast.next.next;//快指针移动两格
            slow = slow.next;//慢指针移动一格
            if(fast == slow){//当快慢指针相遇的时候，就让慢指针和head指针都移动一步，直到head和slow相遇就找到了入环节点
                while(head != slow){
                    slow = slow.next;
                    head = head.next;
                }
                return head;
            }
        }
        return null;

    }
}

Python版本:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def detectCycle(self , head ):
        # write code here
        if head == None:
            return None
        slow = head
        fast = head
        while fast != None and fast.next != None:
            fast = fast.next.next#快指针移动两格
            slow = slow.next#慢指针移动一格
            if slow == fast:#当快慢指针相遇的时候，就让慢指针和head指针都移动一步，直到head和slow相遇就找到了入环节点
                while slow != head:
                    slow = slow.next
                    head = head.next
                return head

        return None

JavaScript版本:

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
function detectCycle( head ) {
    // write code here
    if (head == null) {
        return null;
    }
    let slow = head;
    let fast = head;
    let temp = head;
    while(fast.next != null &amp;&amp; fast.next.next != null){
        slow = slow.next;//慢指针移动一格
        fast = fast.next.next;//快指针移动两格
        if(fast == slow){//当快慢指针相遇的时候，就让慢指针和head指针都移动一步，直到head和slow相遇就找到了入环节点
            while(temp != slow){
                slow = slow.next;
                temp = temp.next;
            }
            return temp;
        }

    }return null;

}
module.exports = {
    detectCycle : detectCycle
};

牛客题霸文章被收录于专栏

本专栏主要是牛客题霸习题的讲解，有详细的考点分类，大家可以可以看看呦！！！