Solution For Linked List Cycle Ii
The Linked List Cycle II problem on LeetCode is a popular problem in the field of data structures and algorithms. It focuses on the concept of linked lists and cycling, and the goal is to detect if there is a cycle in a linked list and return the node at which the cycle begins.
Problem statement
Given a linked list, determine if it has a cycle in it. To represent a cycle in the linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Solution
The problem can be solved using the concept of the two-pointer approach. We can have two pointers, one moving at a slow pace and the other moving at a fast pace. If there is a cycle in the list, then eventually, the fast pointer will catch up with the slow pointer, and they will meet at a node within the cycle. We can then return the node at which the cycle begins.
The following is the algorithm to solve the problem:
- Initialize two pointers, slow and fast, both pointing to the head of the linked list.
- Move the slow pointer by one step and the fast pointer by two steps.
- Continue this process until the fast pointer encounters a null node or a node pointing to the head of the linked list.
- If the fast pointer reaches a null node, then there is no cycle in the list, and we can return null.
- If the fast pointer reaches a node pointing to the head of the list, then the list has a cycle, and we can return the head node as the start of the cycle.
- If the fast pointer encounters the slow pointer while traversing the list, then there is a cycle, and we can return the node where the cycle begins.
The following is the Python implementation of the above algorithm:
“`
class ListNode:
def init(self, x):
self.val = x
self.next = None
def detectCycle(head: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
while head != slow:
head = head.next
slow = slow.next
return head
return None
“`
In the above implementation, we first initialize the slow and fast pointers to the head of the linked list. We then loop through the list, moving the slow pointer by one step and the fast pointer by two steps. If there is no cycle in the list, the fast pointer will eventually reach the end, and the loop will end. We then return null as there is no cycle.
If there is a cycle, then there is a point where the fast pointer will encounter the slow pointer while traversing the list. We then move the head pointer and the slow pointer by one step until they meet. We do this because the head and the slow pointer are k steps away from each other, where k is the distance from the head to the start of the cycle. By moving them both by one step at a time, they will eventually meet at the beginning of the cycle. We then return the head node as the start of the cycle.
Conclusion
The Linked List Cycle II problem on LeetCode is a popular problem in the field of data structures and algorithms. It can be solved using the two-pointer approach, and the Python implementation of the solution is simple and easy to understand.
Step by Step Implementation For Linked List Cycle Ii
/**
* 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 || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (slow != fast) {
return null;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}# 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
"""
# If head is None or head.next is None, then there is no cycle.
if not head or not head.next:
return None
# Use slow and fast pointers to detect if a linked list has a cycle.
# If there is a cycle, slow and fast will eventually meet.
slow = head
fast = head.next
while slow != fast:
# If fast.next is None or fast.next.next is None, then there is no cycle.
if not fast or not fast.next:
return None
# Move slow and fast pointers one node at a time.
slow = slow.next
fast = fast.next.next
# At this point, slow and fast point to the start of the cycle.
# Move slow pointer to head. Then, move both pointers one node at a time
# until they meet again. The meeting point is the start of the cycle.
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
// Floyd's Cycle-Finding Algorithm
var detectCycle = function(head) {
if (!head || !head.next) return null;
let slow = head, fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) break;
}
if (!fast || !fast.next) return null;
slow = head;
while (slow !== fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
};/**
* 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) {
// Use two pointers, slow and fast
// Move slow by 1 and fast by 2 in each iteration
// If they meet, then there is a cycle
if (!head) return NULL;
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
// If fast becomes NULL, then there is no cycle
if (!fast || !fast->next) return NULL;
// Move slow to head. Keep fast at meeting point.
// Each are k steps from the start of the loop.
// If they move at the same pace, they must meet at loop start.
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
};/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode DetectCycle(ListNode head) {
// if head is null or there is only one node in the list, there is no cycle
if (head == null || head.next == null) {
return null;
}
// use slow and fast pointers to detect if there is a cycle
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
// if fast reaches the end of the list, there is no cycle
if (fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
// if there is a cycle, find the starting point of the cycle
slow = head;
while (slow != fast.next) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}