- 1、题目描述:
-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 && 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; } };
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 && 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 && 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 };