Code Destine

Problem Statement

You have given a singly linked list if a linked list contains a cycle, then remove the cycle and return the same linked list. If there is no cycle, then return the same linked list.

Note :- Cycle in the given linked list is represented by an integer position, which represents the position (0-indexed)  in the linked list where the cycle begins. If position is -1, then there is no cycle in the linked list.

Example 

Input :- head = [5, 4, 10, 15, 1, 7], position = 2 (cycle begins at 2nd node)
Output :- head = [5, 4, 10, 15, 1, 7], position = -1 (no cycle in linked list)

Input :- head = [5, 4, 10, 15, 1, 5, 6], position = 3 (cycle begins at 3rd node)
Output :- head = [5, 4, 10, 15, 1, 5, 6], position = -1 (no cycle in linked list)

Solution

This problem can be solved in three steps :-

1. Find whether linked list contains cycle or not.
2. If linked list contains cycle, find the starting node of cycle.
3. Once starting node is found, remove the cycle.

Step 1 :- Floyd’s Cycle-Finding Algorithm can be used to solve the first step. This algorithm uses two variables that move at different speeds and if there is a cycle, both of the variables would point to the same value at some point in the future, for more information see this post.

Create two variables fast and slow, then move both variables together, fast by two nodes and slow by one node till the fast variable reaches the last node or end of the linked list. If fast and slow variables point to the same node before the end of the while loop, then there is a cycle in the linked list otherwise there is no cycle.

Step 2 :- Once the fast and slow variables point to the same node, then set one of them to the head of the Linked List. Now move both of the variables at the same speed. The node where they meet again would be the starting node of the cycle, for more information see this post.

Step 3 :- Once the starting point of the cycle is found, keep one variable (slow) to the starting point and move another variable (fast) by the speed of one node till the fast.next is equals to slow. Now assign null to fast.next.

Program

public class Main {

	public static void main(String[] args) {
		
		ListNode head = null;
		
		ListNode node = new ListNode(5);
		head = node;		
		node.next = new ListNode(4);
		node = node.next;	
		
		ListNode node10 = new ListNode(10);
		node.next = node10;
		node = node.next;
		
		node.next = new ListNode(15);
		node = node.next;		
		node.next = new ListNode(1);
		node = node.next;
		node.next = new ListNode(7);
		node = node.next;
		node.next = node10;
		
		Main main = new Main();
		main.removeCycle(head);	
		
		while(head != null) {			
			System.out.print(head.value+", ");
			head = head.next;
		}
	}
	
	/* Solution */
	public void removeCycle(ListNode head) {
	     
        ListNode point = null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow =slow.next;
            if(fast == slow){
                point = fast;
                break;
            }
        }        
        
        if(point != null){            
            slow = head;
            while(slow != fast){
            	fast = fast.next;
                slow =slow.next;                
            }
            
            while(fast.next != slow) {
            	fast = fast.next;
            }
            fast.next = null;
        }
    }
	
	/* Definition of Linked List Node */
	public static class ListNode {		
		int value;
		ListNode next;
		
		public ListNode(int value) {
			this.value = value;
		}		
	}
}

Result

5, 4, 10, 15, 1, 7, 

That’s all for Remove Cycle from Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.