[数据结构与算法] 环形链表 II （ LeetCode 142 ）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 环形链表 II （ LeetCode 142 ） -> 正文阅读

[数据结构与算法]环形链表 II （ LeetCode 142 ）

题目链接

https://leetcode.cn/problems/linked-list-cycle-ii/

问题解析

请参考https://www.algomooc.com/746.html

代码

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) {
        ListNode slow=head;
        ListNode fast=head;

        while(fast!=null &&fast.next!=null)
        {
            slow=slow.next;
            fast=fast.next.next;

            if(slow==fast)
            {
                ListNode pointhead=head;
                ListNode pointcross=slow;

                while(pointhead!=pointcross)
                {
                    pointhead=pointhead.next;
                    pointcross=pointcross.next;
                }
                return pointcross;
            }
        }
        return null;
    }
}

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) {
        ListNode *slow=head;
        ListNode *fast=head;

        while(fast!=NULL &&fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;

            if(slow == fast)
            {
                ListNode *pointhead=head;
                ListNode *pointcross=fast;
                while(pointhead!=pointcross)
                {
                    pointhead=pointhead->next;
                    pointcross=pointcross->next;
                }
                return pointcross;
            }
        }
        return NULL;
    }
};

python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow=head
        fast=head
        while fast!=None and fast.next!=None:
            slow=slow.next
            fast=fast.next.next

            if slow==fast:
                pointhead=head
                pointcross=fast
                while pointhead!=pointcross:
                    pointhead=pointhead.next
                    pointcross=pointcross.next
                return pointcross
        return None