Given a linked list of N nodes such that it may contain a loop.
A loop here means that the last node of the link list is connected to the node at position X(1-based index). If the link list does not have any loop, X=0.
Remove the loop from the linked list, if it is present, i.e. unlink the last node which is forming the loop.
Example 1:
Input:
N = 3
value[] = {1,3,4}
X = 2
Output: 1
Explanation: The link list looks like
1 -> 3 -> 4
     ^    |
     |____|    
A loop is present. If you remove it 
successfully, the answer will be 1. 
Example 2:
Input:
N = 4
value[] = {1,8,3,4}
X = 0
Output: 1
Explanation: The Linked list does not 
contains any loop. 
Example 3:
Input:
N = 4
value[] = {1,2,3,4}
X = 1
Output: 1
Explanation: The link list looks like 
1 -> 2 -> 3 -> 4
^              |
|______________|
A loop is present. 
If you remove it successfully, 
the answer will be 1. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function removeLoop() which takes the head of the linked list as the input parameter. Simply remove the loop in the list (if present) without disconnecting any nodes from the list.
Note: The generated output will be 1 if your submitted code is correct.
Expected time complexity: O(N)
Expected auxiliary space: O(1)
Constraints:
1 ≤ N ≤ 10^4

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: '''

# node class:



class Node:

    def __init__(self,val):

        self.next=None

        self.data=val



'''



class Solution:

    #Function to remove a loop in the linked list.

    def removeLoop(self, head):

        # code here

        # remove the loop without losing any nodes



Solutions:
class Solution:

	def removeLoop(self, head):
		slow = head
		while slow.next:
			if slow.next.data == float('inf'):
				slow.next = None
				break
			slow.data = float('inf')
			slow = slow.next


class Solution:

	def isLoop(self, head):
		slow = head
		fast = head
		while fast is not None and fast.next is not None:
			fast = fast.next.next
			slow = slow.next
			if fast == slow:
				return slow
		return None

	def removeLoop(self, head):
		p1 = self.isLoop(head)
		if p1 is None:
			return
		p2 = head
		p4 = head
		p3 = None
		if p1 == p4:
			while p4.next != p1:
				p4 = p4.next
		p3 = p4
		while p1 != p2:
			p3 = p1
			p1 = p1.next
			p2 = p2.next
		p3.next = None
		return


class Solution:

	def removeLoop(self, head):
		if not head and (not head.next):
			return 1
		slow_step = head
		fast_step = head
		while slow_step and fast_step and fast_step.next:
			slow_step = slow_step.next
			fast_step = fast_step.next.next
			if fast_step == slow_step:
				break
		if slow_step == head:
			while not fast_step.next == slow_step:
				fast_step = fast_step.next
			fast_step.next = None
		elif slow_step == fast_step:
			slow_step = head
			while not slow_step.next == fast_step.next:
				slow_step = slow_step.next
				fast_step = fast_step.next
			fast_step.next = None
		return


class Solution:

	def removeLoop(self, head):
		if not head and (not head.next):
			return 1
		hashMap = {}
		prev = None
		current = head
		while current:
			if hashMap.get(current, 0):
				prev.next = None
				return
			hashMap[current] = 1
			prev = current
			current = current.next
		return


class Solution:

	def removeLoop(self, head):
		if not head and (not head.next):
			return 1
		hashMap = {}
		prev = None
		current = head
		while current:
			if current in hashMap:
				prev.next = None
				return
			hashMap[current] = True
			prev = current
			current = current.next
		return


def isloop(head):
	(fast, slow) = (head, head)
	if head == None:
		return 0
	while fast != None and fast.next != None:
		fast = fast.next.next
		slow = slow.next
		if fast == slow:
			return fast
	return None

class Solution:

	def removeLoop(self, head):
		temp = isloop(head)
		if temp == None:
			return
		slow = head
		while temp != slow:
			temp = temp.next
			slow = slow.next
		while slow.next != temp:
			slow = slow.next
		slow.next = None
		return head


class Solution:

	def detectLoop(self, head):
		slow_p = head
		fast_p = head
		while True:
			if slow_p is None or fast_p is None:
				return False
			slow_p = slow_p.next
			if fast_p.next is None:
				return False
			fast_p = fast_p.next.next
			if fast_p == slow_p:
				return fast_p
		return False

	def removeLoop(self, head):
		poc = self.detectLoop(head)
		prev = None
		t1 = head
		t2 = poc
		if poc:
			if t1 == t2:
				while t1.next != t2:
					t1 = t1.next
				t1.next = None
				return
			while t1 != t2:
				t1 = t1.next
				prev = t2
				t2 = t2.next
			if prev:
				prev.next = None


class Solution:

	def removeLoop(self, head):
		temp = head
		prev = head
		while temp != None:
			if temp.data == -4:
				prev.next = None
				return
			prev = temp
			temp.data = -4
			temp = temp.next


class Solution:

	def removeLoop(self, head):
		slow = head
		fast = head
		t = None
		flag = False
		while fast.next != None and fast.next.next != None:
			fast = fast.next.next
			slow = slow.next
			if slow == fast:
				flag = True
				break
		if flag == False:
			return head
		if slow == head:
			while slow.next != head:
				slow = slow.next
			slow.next = None
			return head
		slow = head
		while slow.next != fast.next:
			slow = slow.next
			fast = fast.next
		fast.next = None
		return head


class Solution:

	def removeLoop(self, head):
		fast = head.next
		slow = head
		while fast != slow:
			if fast is None or fast.next is None:
				return
			fast = fast.next.next
			slow = slow.next
		size = 1
		fast = fast.next
		while fast != slow:
			fast = fast.next
			size += 1
		slow = head
		fast = head
		for _ in range(size - 1):
			fast = fast.next
		while fast.next != slow:
			fast = fast.next
			slow = slow.next
		fast.next = None


class Solution:

	def removeLoop(self, head):
		slow = head
		fast = head
		prev1 = None
		while slow.next and fast.next and fast.next.next:
			prev1 = slow
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if slow != fast:
			return
		if slow == head:
			prev1.next = None
			return
		start = head
		prev = slow
		while start != slow:
			prev = slow
			start = start.next
			slow = slow.next
		prev.next = None


class Solution:

	def removeLoop(self, head):
		if head is None or head.next is None:
			return
		slow = head
		fast = head
		while fast is not None and fast.next is not None:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if slow != fast:
			return
		len = 1
		fast = fast.next
		while fast != slow:
			fast = fast.next
			len += 1
		ptr1 = head
		ptr2 = head
		for i in range(len):
			ptr1 = ptr1.next
		while ptr1 != ptr2:
			ptr1 = ptr1.next
			ptr2 = ptr2.next
		while ptr2.next != ptr1:
			ptr2 = ptr2.next
		ptr2.next = None


class Solution:

	def removeLoop(self, head):
		Freq = {}
		total_nodes = 0
		pos = 0
		prev = None
		temp = head
		while temp != None:
			if temp not in Freq:
				pos += 1
				Freq[temp] = pos
				total_nodes += 1
			else:
				break
			prev = temp
			temp = temp.next
		prev.next = None


class Solution:

	def removeLoop(self, head):
		Freq = {}
		temp = head
		prev = None
		while temp != None:
			if temp not in Freq:
				Freq[temp] = 1
			else:
				break
			prev = temp
			temp = temp.next
		if temp != None:
			prev.next = None
			return head
		else:
			return head


class Solution:

	def removeLoop(self, head):
		itr = head
		s = set()
		while itr:
			if itr.next in s:
				itr.next = None
				return head
			else:
				s.add(itr)
				itr = itr.next
		return head


class Solution:

	def removeLoop(self, head):
		slow = head
		fast = head
		loopExist = False
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				loopExist = True
				break
		if loopExist:
			loopStart = head
			while loopStart != slow:
				loopStart = loopStart.next
				slow = slow.next
			prev = slow
			while prev.next != slow:
				prev = prev.next
			prev.next = None


class Solution:

	def removeLoop(self, head):
		low = head
		high = head
		while low != None and high != None and (high.next != None):
			low = low.next
			high = high.next.next
			if low == high:
				break
		if low == head:
			while high.next != low:
				high = high.next
			high.next = None
		elif low == high:
			low = head
			while low.next != high.next:
				low = low.next
				high = high.next
			high.next = None


class Solution:

	def removeLoop(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if not fast or not fast.next:
			return head
		ptr1 = head
		ptr2 = slow
		while ptr1 != ptr2:
			ptr1 = ptr1.next
			ptr2 = ptr2.next
		while ptr2.next != ptr1:
			ptr2 = ptr2.next
		ptr2.next = None
		return head


class Solution:

	def removeLoop(self, head):
		slow = head
		fast = head
		while slow and fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		slow = head
		while slow != fast and fast != None:
			slow = slow.next
			fast = fast.next
		tmp = slow
		while tmp.next != None and tmp.next != slow:
			tmp = tmp.next
		if tmp.next == slow:
			tmp.next = None
			return 1
		else:
			return 0


class Solution:

	def removeLoop(self, head):
		front = head
		second = head
		while second != None:
			front = front.next
			if second.next is not None:
				second = second.next.next
			else:
				second = second.next
			if second == front:
				front = head
				while front != second:
					front = front.next
					second = second.next
				front = second
				while front.next != second:
					front = front.next
				front.next = None
				return
		return


class Solution:

	def removeLoop(self, head):
		meet = self.detectLoop(head)
		if meet is None:
			return head
		if meet == head:
			curr = head
			while curr.next != head:
				curr = curr.next
			curr.next = None
			return head
		curr = head
		while meet != curr:
			prev = meet
			meet = meet.next
			curr = curr.next
		prev.next = None
		return head

	def detectLoop(self, head):
		(slow, fast) = (head, head)
		while fast is not None and fast.next is not None:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				return slow
		return None


class Solution:

	def removeLoop(self, head):
		d = {}
		d[head] = 1
		while head.next != None:
			if head.next in d:
				head.next = None
				break
			else:
				d[head.next] = 1
				head = head.next


class Solution:

	def removeLoop(self, head):
		headMap = {}
		headMap[head] = 1
		while head.next is not None:
			w = headMap.get(head.next, 0) + 1
			headMap[head.next] = w
			if w == 2:
				head.next = None
				break
			head = head.next


class Solution:

	def removeLoop(self, head):
		if not head.next:
			return head
		temp = head.next
		temp2 = head.next.next
		while temp2 and temp2.next and (temp != temp2):
			temp = temp.next
			temp2 = temp2.next.next
		if not temp2 or not temp2.next:
			return head
		temp = head
		while temp != temp2:
			temp = temp.next
			temp2 = temp2.next
		temps = temp2
		while temps.next != temp:
			temps = temps.next
		temps.next = None
		return head


class Solution:

	def removeLoop(self, head):
		if head is None or head.next is None:
			return
		slowPtr = head
		fastPtr = head
		while fastPtr is not None and fastPtr.next is not None:
			slowPtr = slowPtr.next
			fastPtr = fastPtr.next.next
			if slowPtr == fastPtr:
				break
		if slowPtr != fastPtr:
			return
		count = 1
		tempPtr = slowPtr
		while tempPtr.next != slowPtr:
			count += 1
			tempPtr = tempPtr.next
		ptr1 = head
		ptr2 = head
		for _ in range(count):
			ptr2 = ptr2.next
		while ptr1 != ptr2:
			ptr1 = ptr1.next
			ptr2 = ptr2.next
		while ptr2.next != ptr1:
			ptr2 = ptr2.next
		ptr2.next = None


class Solution:

	def removeLoop(self, head):
		slow = Node(None)
		slow.next = head
		head = fast = slow
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if fast == slow:
				slow = head
				while fast.next != slow.next:
					fast = fast.next
					slow = slow.next
				fast.next = None
				return


class Solution:

	def removeLoop(self, head):
		slow = head
		fast = head
		while fast is not None and fast.next is not None:
			fast = fast.next.next
			slow = slow.next
			if fast == slow:
				break
		if slow == head:
			fast = fast.next
			while fast.next != head:
				fast = fast.next
			fast.next = None
		if slow == fast:
			slow = head
			while slow.next != fast.next:
				slow = slow.next
				fast = fast.next
			fast.next = None


class Solution:

	def removeLoop(self, head):
		if head.next == None:
			return
		t = head
		t.data = -1
		while t.next != None:
			if t.next.data == -1:
				t.next = None
				break
			elif t.next == None:
				return
			t = t.next
			t.data = -1


class Solution:

	def removeLoop(self, head):
		dict = {}
		temp = head
		while temp.next != None:
			if temp.next in dict:
				temp.next = None
				return 1
			else:
				dict[temp] = 1
			temp = temp.next
		return 0


class Solution:

	def removeLoop(self, head):
		tmp = head
		while True:
			if tmp.next == None:
				break
			if tmp.next.data == 'a':
				tmp.next = None
				break
			tmp.data = 'a'
			tmp = tmp.next


class Solution:

	def removeLoop(self, head):
		fast = head.next
		slow = head
		while fast != slow:
			if fast is None or fast.next is None:
				return
			fast = fast.next.next
			slow = slow.next
		length = 1
		fast = fast.next
		while fast != slow:
			fast = fast.next
			length += 1
		slow = head
		fast = head
		for i in range(length - 1):
			fast = fast.next
		while fast.next != slow:
			fast = fast.next
			slow = slow.next
		fast.next = None


class Solution:

	def removeLoop(self, head):
		fast = head
		slow = head
		while fast and fast.next:
			fast = fast.next.next
			slow = slow.next
			if fast == slow:
				break
		if fast == None or fast.next == None:
			return
		size = 0
		fast = fast.next
		while fast != slow:
			fast = fast.next
			size += 1
		slow = head
		fast = head
		for _ in range(size):
			fast = fast.next
		while fast.next != slow:
			fast = fast.next
			slow = slow.next
		fast.next = None


class Solution:

	def removeLoop(self, head):
		d = set()
		prev = None
		cur = head
		while cur:
			if cur in d:
				prev.next = None
				return
			else:
				d.add(cur)
				prev = cur
				cur = cur.next


class Solution:

	def loop(self, head):
		slow = head
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				return slow
		return None

	def removeLoop(self, head):
		flag = self.loop(head)
		if flag == None:
			return head
		else:
			s = flag
			f = head
			while f != s:
				f = f.next
				s = s.next
			cur = head
			flag = 0
			start = s
			while start:
				if start.next == s:
					start.next = None
				start = start.next
			return head


class Solution:

	def removeLoop(self, head):
		s = set([head])
		while head.next != None:
			if head.next in s:
				head.next = None
				break
			else:
				s.add(head.next)
			head = head.next


class Solution:

	def removeLoop(self, head):
		slow = head
		fast = head
		while fast.next and fast.next.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if slow == fast:
			slow = head
			if fast == slow:
				while fast.next != slow:
					fast = fast.next
			else:
				while fast.next != slow.next:
					slow = slow.next
					fast = fast.next
			fast.next = None
		return head


class Node:

	def __init__(self, val):
		self.next = None
		self.data = val

class Solution:

	def removeLoop(self, head):
		(slow, fast) = (head, head)
		t = 0
		while slow and fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				t = 1
				break
		if t:
			slow = head
			if slow == fast:
				while fast.next != slow:
					fast = fast.next
			else:
				while slow.next != fast.next:
					slow = slow.next
					fast = fast.next
			fast.next = None
		return head


class Solution:

	def removeLoop(self, head):
		mp = {}
		tmp = head
		while head:
			mp[head] = True
			if head.next in mp:
				head.next = None
				break
			head = head.next
		return tmp


class Solution:

	def removeLoop(self, head):
		slow = fast = head
		while slow and fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if slow == head:
			while fast.next != slow:
				fast = fast.next
			fast.next = None
		elif slow == fast:
			slow = head
			while slow.next != fast.next:
				slow = slow.next
				fast = fast.next
			fast.next = None
		else:
			pass


class Solution:

	def removeLoop(self, head):
		prev = None
		s = set()
		while head != None:
			if head in s:
				prev.next = None
				break
			s.add(head)
			prev = head
			head = head.next
		return head


class Solution:

	def removeLoop(self, head):
		map_ = {}
		curr = head
		while curr.next != None and curr.next not in map_:
			map_[curr] = True
			curr = curr.next
		curr.next = None


class Solution:

	def removeLoop(self, head):
		mp = set()
		prev = None
		while head is not None:
			if head in mp:
				prev.next = None
				return True
			else:
				mp.add(head)
				prev = head
				head = head.next
		return False


class Solution:

	def removeLoop(self, head):
		curr = head
		visited_nodes = set()
		while curr.next is not None:
			if curr.next in visited_nodes:
				break
			visited_nodes.add(curr)
			curr = curr.next
		curr.next = None


class Solution:

	def removeLoop(self, head):
		seen = set()
		curr = head
		startOfLoop = None
		while True:
			if not curr.next:
				return
			if curr in seen:
				startOfLoop = curr
				break
			seen.add(curr)
			curr = curr.next
		curr = startOfLoop
		while True:
			if curr.next == startOfLoop:
				curr.next = None
				break
			curr = curr.next
		return


class Solution:

	def removeLoop(self, head):
		l = set()
		cur = head
		while cur:
			if cur.next in l:
				cur.next = None
			l.add(cur)
			cur = cur.next


class Solution:

	def removeLoop(self, start):
		slow = start
		fast = start.next
		while fast:
			slow = slow.next
			fast = fast.next
			if fast:
				fast = fast.next
			if slow == fast:
				break
		else:
			return 0
		slow = start
		count = 1
		while slow != fast.next:
			slow = slow.next
			fast = fast.next
		fast.next = None


class Solution:

	def removeLoop(self, start):
		slow = start
		fast = start.next
		while fast and fast != slow:
			slow = slow.next
			fast = fast.next
			if fast:
				fast = fast.next
		if fast is None:
			return 0
		slow = start
		while slow != fast.next:
			slow = slow.next
			fast = fast.next
		fast.next = None


class Solution:

	def removeLoop(self, head):

		def detect(head):
			slow = head
			fast = head
			while slow and fast:
				slow = slow.next
				fast = fast.next
				if fast:
					fast = fast.next
				if slow == fast:
					return slow
			return None
		slow = detect(head)
		if slow == None:
			return None
		temp = head
		prev = None
		while temp != slow:
			temp = temp.next
			slow = slow.next
		k = temp
		while temp.next != k:
			temp = temp.next
		temp.next = None


class Solution:

	def removeLoop(self, head):
		dic = {}
		temp = head
		while temp != None:
			if temp in dic:
				prev.next = None
				break
			else:
				dic[temp] = 1
			prev = temp
			temp = temp.next


class Solution:

	def removeCycle(self, slow, head):
		curr = head
		while curr:
			ptr = slow
			while ptr.next is not slow and ptr.next is not curr:
				ptr = ptr.next
			if ptr.next == curr:
				ptr.next = None
				return
			curr = curr.next

	def identifyCycle(self, head):
		slow = fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				return slow
		return None

	def removeLoop(self, head):
		slow = head
		fast = head
		while fast != None and fast.next != None:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				break
		if fast == None or fast.next == None:
			return
		temp = head
		while temp != fast:
			temp = temp.next
			fast = fast.next
		while temp.next != fast:
			temp = temp.next
		temp.next = None


class Solution:

	def removeLoop(self, head):
		s = head
		f = head
		while f.next != None or f.next.next != None:
			s = s.next
			f = f.next.next
			if f.next == None:
				return
			if f.next.next == None:
				return
			if s == f:
				break
		if f.next == None or f.next.next == None:
			return
		s = head
		while s.next != f.next:
			s = s.next
			f = f.next
		if f == head:
			while f.next != s:
				f = f.next
		f.next = None


class Solution:

	def removeLoop(self, head):
		slow = head
		fast = head
		loopExists = False
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
			if slow == fast:
				loopExists = True
				break
		if loopExists:
			length = 1
			temp = slow
			while temp.next != slow:
				length += 1
				temp = temp.next
			ptr1 = head
			ptr2 = head
			for i in range(length):
				ptr2 = ptr2.next
			while ptr1 != ptr2:
				ptr1 = ptr1.next
				ptr2 = ptr2.next
			while ptr2.next != ptr1:
				ptr2 = ptr2.next
			ptr2.next = None


class Solution:

	def removeLoop(self, head):
		curr = head
		while curr.next != None and curr.next.data != -1:
			curr.data = -1
			curr = curr.next
		curr.next = None
		return head


class Solution:

	def removeLoop(self, head):
		slowPtr = fastPtr = head
		while fastPtr and fastPtr.next:
			prev = slowPtr
			slowPtr = slowPtr.next
			fastPtr = fastPtr.next.next
			if slowPtr == fastPtr:
				startPtr = head
				while startPtr != slowPtr:
					prev = slowPtr
					slowPtr = slowPtr.next
					startPtr = startPtr.next
				prev.next = None


class Solution:

	def removeLoop(self, h):
		s = h
		f = h.next
		while f != s:
			if f is None or f.next is None:
				return
			s = s.next
			f = f.next.next
		size = 1
		f = f.next
		while f != s:
			f = f.next
			size += 1
		s = h
		f = h
		for i in range(size - 1):
			f = f.next
		while f.next != s:
			f = f.next
			s = s.next
		f.next = None


class Solution:

	def removeLoop(self, head):
		temp1 = temp2 = head
		prev = None
		while temp1 != None and temp2 != None and (temp2.next != None):
			temp1 = temp1.next
			prev = temp2.next
			temp2 = temp2.next.next
			if temp1 == temp2:
				break
		temp3 = head
		if temp3 == temp1:
			prev.next = None
		else:
			while temp3 != None and temp2 != None:
				prev = temp2
				temp3 = temp3.next
				temp2 = temp2.next
				if temp3 == temp2:
					prev.next = None
					break


class Solution:

	def removeLoop(self, head):
		if head == None:
			return
		temp1 = head
		temp2 = None
		s = set()
		while temp1 != None:
			if temp1 in s:
				temp2.next = None
				return
			s.add(temp1)
			temp2 = temp1
			temp1 = temp1.next


class Solution:

	def removeLoop(self, head):
		mpp = {}
		temp = head
		while True:
			mpp[temp] = True
			if temp.next == None:
				return
			elif temp.next in mpp:
				temp.next = None
				return
			temp = temp.next
		return


def find(head):
	fast = head
	slow = head
	while fast != None and fast.next != None:
		fast = fast.next.next
		slow = slow.next
		if slow == fast:
			return slow
	return 1

def get(head):
	inter = find(head)
	if inter == 1:
		return 1
	slow = head
	while slow != inter:
		slow = slow.next
		inter = inter.next
	return slow

class Solution:

	def removeLoop(self, head):
		start = get(head)
		if start == 1:
			return 1
		temp = start
		while temp.next != start:
			temp = temp.next
		temp.next = None
		ans = find(head)
		return ans


class Solution:

	def removeLoop(self, head):
		d = {}
		curr = head
		d[head] = 1
		while curr.next:
			if curr.next in d:
				curr.next = None
				return 1
			else:
				d[curr.next] = 1
			curr = curr.next


class Solution:

	def removeLoop(self, head):
		if head == None:
			return None
		if head.next == None:
			return head
		slow = head
		fast = head.next
		prev = None
		l = set()
		while slow and fast and fast.next:
			if slow in l:
				prev.next = None
				return head
			else:
				l.add(slow)
				prev = slow
				slow = slow.next