Remove Cycle: Modify the next pointer of the last node in the cycle to remove the cycle. Please go through 1 and 2 before continuing this post for better understanding.
publicclassSolution {
publicvoidremoveCycle(ListNode head) {
ListNode slow = head, fast = head;
// Step 1: Detect cycle using Floyd’s Tortoise and Hare Algorithmwhile (fast !=null&& fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // Cycle detected breakCycle(head, slow);
return;
}
}
}
privatevoidbreakCycle(ListNode head, ListNode meetingPoint) {
ListNode start = head;
ListNode cycleNode = meetingPoint;
// Step 2: Find the entry point of the cyclewhile (start != cycleNode) {
start = start.next;
cycleNode = cycleNode.next;
}
// Step 3: Find the last node in the cycle and break the cycle ListNode lastNode = cycleNode;
while (lastNode.next!= cycleNode) {
lastNode = lastNode.next;
}
lastNode.next=null; // Remove the cycle }
// Helper function to create a cycle for testingpublicvoidcreateCycle(ListNode head, int pos) {
if (pos ==-1)
return;
ListNode tail = head, cycleEntry =null;
int index = 0;
while (tail.next!=null) {
if (index == pos) {
cycleEntry = tail;
}
tail = tail.next;
index++;
}
tail.next= cycleEntry; // Create the cycle }
// Helper function to print the linked listpublicvoidprintLinkedList(ListNode head) {
ListNode current = head;
while (current !=null) {
System.out.print(current.val+" -> ");
current = current.next;
}
System.out.println("None");
}
// Helper function to create a linked list from an arraypublic ListNode createLinkedList(int[] arr) {
if (arr.length== 0)
returnnull;
ListNode dummy =new ListNode(0);
ListNode current = dummy;
for (int value : arr) {
current.next=new ListNode(value);
current = current.next;
}
return dummy.next;
}
publicstaticvoidmain(String[] args) {
Solution solution =new Solution();
int[] arr1 = {3, 2, 0, -4};
ListNode head1 = solution.createLinkedList(arr1);
solution.createCycle(head1, 1);
System.out.println("Linked List with Cycle:");
solution.printLinkedList(
head1); // This will print indefinitely if there is a cycle solution.removeCycle(head1);
System.out.println("Linked List after removing Cycle:");
solution.printLinkedList(head1);
}
}
classSolution:
defremoveCycle(self, head: ListNode) ->None:
slow, fast = head, head
# Step 1: Detect cycle using Floyd’s Tortoise and Hare Algorithmwhile fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # Cycle detected self.breakCycle(head, slow)
returndefbreakCycle(self, head: ListNode, meetingPoint: ListNode) ->None:
start, cycleNode = head, meetingPoint
# Step 2: Find the entry point of the cyclewhile start != cycleNode:
start = start.next
cycleNode = cycleNode.next
# Step 3: Find the last node in the cycle and break the cycle lastNode = cycleNode
while lastNode.next != cycleNode:
lastNode = lastNode.next
lastNode.next =None# Remove the cycle# Helper function to create a cycle for testingdefcreate_cycle(head: ListNode, pos: int) ->None:
if pos ==-1:
return tail, cycleEntry = head, None index =0while tail.next:
if index == pos:
cycleEntry = tail
tail = tail.next
index +=1if cycleEntry:
tail.next = cycleEntry # Create the cycle# Helper function to print the linked listdefprint_linked_list(head: ListNode) ->None:
current = head
visited = set()
while current:
if current in visited:
print(f"{current.val}(cycle starts here) -> ", end="")
break print(f"{current.val} -> ", end="")
visited.add(current)
current = current.next
print("None")
# Helper function to create a linked list from an arraydefcreate_linked_list(arr) -> ListNode:
ifnot arr:
returnNone dummy = ListNode(0)
current = dummy
for val in arr:
current.next = ListNode(val)
current = current.next
return dummy.next
# Example usagearr1 = [3, 2, 0, -4]
head1 = create_linked_list(arr1)
create_cycle(head1, 1)
print("Linked List with Cycle:")
print_linked_list(head1) # This will print indefinitely if there is a cyclesolution = Solution()
solution.removeCycle(head1)
print("Linked List after removing Cycle:")
print_linked_list(head1)