Given a singly linked list, your task is to remove every k^{th} node from the linked list.
Input:
The first line of input contains number of test cases T. Then T test cases follow. Every test case contains 3 lines. First line of every test case contains an integer N denoting the size of the linked list . The second line contains N space separated values of the linked list. The third line contains an integer K.
Output:
Output for each test case will be space separated values of the nodes of the new transformed linked list.
User Task:
The task is to complete the function deleteK() which should delete every kth nodes from the linked list.
Constraints:
1 <= T <= 50
1 <= N <= 100
1 <= element of linked list <= 1000
0 <= k <= 100
Example:
Input:
2
8
1 2 3 4 5 6 7 8
3
4
1 2 3 4
2
Output:
1 2 4 5 7 8
1 3
Explanation:
Testcase 1: After removing every 3rd element from the linked list, we have updated list as 1, 2, 4, 5, 7 and 8, and the elements which are removed are 3 and 6.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #Your task is to complete this function

#Your function should return the new head pointer

def deleteK(head, k):

    #code here

Solutions:
def deleteK(head, k):
	n = head
	s = 1
	if k == 1:
		return None
	while n != None:
		s = s + 1
		while n.next != None and s == k:
			n.next = n.next.next
			s = 1
		n = n.next
	return head


def freelist(node):
	while node != None:
		next = node.next
		node = next
	return node

def deleteK(head, k):
	temp = head
	count = 0
	if head == None:
		return None
	if k == 1:
		freelist(head)
		return None
	else:
		while temp and temp.next:
			count += 1
			if count == k - 1:
				temp.next = temp.next.next
				count = 0
			temp = temp.next
	return head


def deleteK(head, k):
	if k == 1:
		head = None
		return head
	counter = 1
	curr_node = head
	prev_node = None
	while curr_node:
		if counter == k:
			prev_node.next = curr_node.next
			prev_node = curr_node
			curr_node = curr_node.next
			counter = 1
		else:
			prev_node = curr_node
			curr_node = curr_node.next
			counter += 1
	return head


def deleteK(head, k):
	temp = head.next
	prev = head
	count = 2
	if k == 1:
		head = None
		return head
	while temp != None:
		if count != k:
			temp = temp.next
			prev = prev.next
			count += 1
		elif count == k:
			count = 1
			temp = temp.next
			prev.next = temp
	return head


def deleteK(head, k):
	(cc, temp) = (2, head)
	if k == 1:
		return None
	if k == 0:
		return head
	while temp.next:
		if cc % k == 0:
			if temp.next.next:
				temp.next = temp.next.next
			elif temp.next:
				temp.next = None
		else:
			temp = temp.next
		cc += 1
	return head


def deleteK(head, k):
	temp = head
	count = 1
	prev_temp = None
	while temp:
		if count == k:
			if prev_temp == None:
				head = head.next
				head = None
			else:
				prev_temp.next = temp.next
				count = 0
		count += 1
		prev_temp = temp
		temp = temp.next
	return head


def deleteK(head, k):
	if k == 0:
		return head
	if k == 1:
		return None
	temp = head
	next_index = 2
	while temp.next:
		if next_index % k == 0:
			temp.next = temp.next.next
			next_index += 1
		else:
			temp = temp.next
			next_index += 1
	return head


def deleteK(head, k):
	if k == 1:
		return None
	tmp = head
	while head:
		c = k
		while head and c - 2:
			head = head.next
			c -= 1
		if head and head.next:
			head.next = head.next.next
		if head:
			head = head.next
	return tmp


def deleteK(head, k):

	def delete(prev, ptr):
		temp = ptr.next
		prev.next = temp
		del ptr
		return temp
	prev = None
	x = 1
	ptr = head
	while ptr:
		if k == 1:
			del head
			return None
		if x == k:
			ptr = delete(prev, ptr)
			x = 1
		else:
			prev = ptr
			ptr = ptr.next
			x += 1
	return head


def deleteK(head, k):
	temp = head
	c = 0
	if k == 1:
		return
	else:
		while temp:
			c = c + 1
			if c + 1 == k:
				if temp.next is None:
					break
				else:
					temp.next = temp.next.next
					c = 0
			temp = temp.next
		return head


def deleteK(head, k):
	if head is None or k == 1:
		return None
	if k == 0:
		return head
	prev = None
	cur = head
	c = 0
	while cur != None:
		c += 1
		if c % k == 0 and prev != None:
			prev.next = cur.next
			cur = cur.next
		else:
			prev = cur
			cur = cur.next
	return head


def deleteK(head, k):
	if k == 0:
		return head
	if k == 1:
		return None
	c = 0
	h = head
	while head and head.next:
		c += 1
		if (c + 1) % k == 0:
			a = head.next.next
			head.next = a
		else:
			head = head.next
	return h


def deleteK(head, k):
	if k == 1:
		return None
	t = head
	i = 0
	while t and t.next:
		i += 1
		if i == k - 1:
			t.next = t.next.next
			i = 0
		t = t.next
	return head


def deleteK(head, k):
	if k == 0:
		return head
	if k == 1:
		return None
	temp = head
	c = 1
	while temp:
		c += 1
		if c % k == 0 and temp.next != None:
			temp.next = temp.next.next
		else:
			temp = temp.next
	return head


def deleteK(head, k):
	temp = head
	c = 1
	if head is None or k == 1:
		return None
	if k == 0:
		return head
	while temp != None and temp.next != None:
		c += 1
		if c == k:
			temp.next = temp.next.next
			c = 1
		temp = temp.next
	return head


def deleteK(head, k):
	curr = head
	prev = None
	i = 1
	while curr:
		if k == 0:
			return head
		if i % k == 0:
			if not prev:
				head = head.next
				curr = head
			else:
				prev.next = curr.next
				curr = prev.next
		else:
			prev = curr
			curr = curr.next
		i += 1
	return head


def deleteK(head, k):
	curr = head
	counter = 1
	if k == 1:
		return None
	while curr != None:
		if counter == k - 1:
			if curr.next == None:
				return head
			curr.next = curr.next.next
			counter = 1
			curr = curr.next
			continue
		curr = curr.next
		counter += 1
	return head


def deleteK(head, k):
	if head is None or k == 1:
		return None
	if k == 0:
		return head
	a = head
	count = 1
	while a is not None and a.next is not None:
		count += 1
		if count == k:
			a.next = a.next.next
			count = 1
		a = a.next
	return head


def deleteK(head, k):
	if k == 1:
		return None
	t = head
	cnt = 1
	while t is not None and t.next is not None:
		cnt += 1
		if cnt == k:
			cnt = 1
			t.next = t.next.next
		t = t.next
	return head


def deleteK(head, k):
	current = head
	i = 0
	if k == 1:
		return None
	if k == 0 or not head:
		return head
	while current and current.next:
		i += 1
		if (i + 1) % k == 0:
			current.next = current.next.next
		else:
			current = current.next
	return head


def deleteK(head, k):
	if k == 0 or not head:
		return head
	if k == 1:
		return None
	position = 0
	curr = head
	while curr and curr.next:
		position += 1
		if (position + 1) % k == 0:
			curr.next = curr.next.next
		else:
			curr = curr.next
	return head


def deleteK(head, k):
	if k == 0:
		return head
	if k == 1:
		return None
	cur = head
	prev = None
	i = 0
	while cur:
		i += 1
		if i % k == 0:
			if prev:
				prev.next = cur.next
			else:
				head = cur.next
		prev = cur
		cur = cur.next
	return head


def deleteK(head, k):
	curr = head
	i = 1
	if k == 1:
		head = None
		return head
	while curr:
		if i == k - 1:
			if curr.next is not None:
				nextnode = curr.next
				curr.next = nextnode.next
			i = 0
		curr = curr.next
		i += 1
	return head


def deleteK(head, k):
	temp = head
	if k == 1:
		return None
	i = 1
	while temp.next != None:
		if i == k - 1:
			temp.next = temp.next.next
			i = 0
		else:
			temp = temp.next
			i += 1
	return head


def deleteK(head, k):
	if not head or k == 1:
		return None
	(prev, cur, count) = (None, head, 0)
	while cur:
		count += 1
		if count == k:
			count = 0
			prev.next = cur.next
		if count:
			prev = cur
		cur = prev.next
	return head


def deleteK(head, k):
	if k == 1:
		return None
	if k == 0:
		return head
	prev = None
	curr = head
	count = 1
	while curr != None:
		if count % k == 0:
			prev.next = curr.next
			prev = prev.next
			curr = prev
		else:
			prev = curr
			curr = curr.next
		count += 1
	return head


def deleteK(head, k):
	if head is None:
		return None
	temp = head
	back = None
	n = 1
	if k == 1:
		return
	while temp != None and temp.next != None:
		n += 1
		back = temp
		temp = temp.next
		if n == k:
			r = temp.next
			del temp
			back.next = r
			temp = r
			n = 1
	return head


def deleteK(head, k):
	a = head
	prev = None
	c = 1
	if c == k:
		return None
	while a:
		if c == k:
			c = 1
			prev.next = a.next
			a = a.next
		else:
			prev = a
			c += 1
			a = a.next
	return head


def deleteK(head, k):
	if k == 1:
		return None
	count = 1
	cur = head
	while cur and cur.next:
		if count + 1 == k:
			cur.next = cur.next.next
			cur = cur.next
			count = 1
		else:
			count += 1
			cur = cur.next
	return head


def deleteK(head, k):
	res = Linked_List()
	cnt = 1
	cur = head
	if k == 0:
		return head
	while cur:
		if cnt % k != 0:
			res.insert(cur.data)
		cnt += 1
		cur = cur.next
	return res.head


def deleteK(head, k):
	if k == 1:
		return None
	if k == 0:
		return head
	ptr = head
	prev = None
	count = 0
	while ptr != None:
		count = count + 1
		if k == count:
			prev.next = ptr.next
			count = 0
		if count != 0:
			prev = ptr
		ptr = prev.next
	return head


def deleteK(head, k):
	if k == 1:
		return None
	if k == 0:
		return head
	prev = None
	temp = head
	r = 1
	while temp:
		if r % k == 0:
			if temp == None:
				prev.next = temp
				break
			prev.next = temp.next
			temp = prev.next
		else:
			prev = temp
			temp = prev.next
		r += 1
	return head


def deleteK(head, k):
	prev = None
	j = 0
	temp = head
	if k == 1:
		return None
	while temp:
		j += 1
		if j == k:
			j = 0
			prev.next = temp.next
		prev = temp
		temp = temp.next
	return head


def deleteK(head, k):
	if k == 0:
		return head
	if k == 1:
		return None
	cur = head
	a = 1
	while cur.next != None:
		if a % (k - 1) == 0:
			a = 1
			cur.next = cur.next.next
			if cur.next == None:
				break
			else:
				cur = cur.next
		else:
			cur = cur.next
			a += 1
	return head


def deleteK(head, k):
	c = 0
	fast = head
	slow = None
	if k == 1:
		return None
	while fast:
		c = c + 1
		if c == k:
			slow.next = fast.next
			c = 0
		slow = fast
		fast = fast.next
	return head


def deleteK(head, k):
	if k == 1:
		return None
	elif k == 0:
		return head
	n = head
	count = 0
	p = None
	headp = None
	while n != None:
		count += 1
		if count < k:
			if p == None:
				p = n
				headp = n
			else:
				p.next = n
				p = p.next
			if count == k - 1:
				if n.next != None:
					n.next = n.next.next
				else:
					break
			else:
				n = n.next
		else:
			count = 0
			n = n.next
	if p != None:
		p.next = None
	if headp == None:
		return None
	return headp


def deleteK(head, k):
	n = head
	if k == 1:
		return None
	count = 0
	while n != None:
		count += 1
		if count == k - 1 and n.next != None:
			n.next = n.next.next
			count = 0
		n = n.next
	return head


def deleteK(head, k):
	ptr = head
	if k == 0:
		return head
	if k == 1:
		return None
	for i in range(k - 2):
		if ptr is None:
			return head
		ptr = ptr.next
	if ptr.next is None:
		return head
	ptr.next = ptr.next.next
	while True:
		for i in range(k - 1):
			if ptr is None:
				break
			ptr = ptr.next
		if ptr is None or ptr.next is None:
			break
		ptr.next = ptr.next.next
	return head


def deleteK(head, k):
	tmp = head
	ctr = 1
	if k == 1:
		return None
	while tmp:
		if ctr == k - 1:
			if not tmp.next:
				break
			tmp.next = tmp.next.next
			ctr = 0
		ctr += 1
		tmp = tmp.next
	return head


def deleteK(head, k):
	temp = head
	j = 1
	while temp:
		temp = temp.next
	if j == k:
		return None
	curr = head
	prev = head
	i = 1
	while curr.next:
		curr = curr.next
		i += 1
		if i == k:
			prev.next = curr.next
			curr = curr.next
			i = 1
		prev = curr
		if curr == None:
			break
	return head


def deleteK(head, k):
	if head == None:
		return
	if k == 1:
		return None
	if k == 0:
		return head
	i = 2
	cur = head
	while cur.next != None:
		if i % k == 0:
			if cur.next.next:
				cur.next = cur.next.next
			elif cur.next:
				cur.next = None
		else:
			cur = cur.next
		i += 1
	return head


def deleteK(head, k):
	count = 0
	if k == 1:
		return None
	ptr = head
	while ptr is not None:
		count += 1
		if count == k - 1:
			if ptr.next is not None:
				ptr.next = ptr.next.next
				ptr = ptr.next
				count = 0
			else:
				ptr = ptr.next
		else:
			ptr = ptr.next
	return head


def deleteK(head, k):
	count = 1
	node = head
	prev = head
	if k == 1:
		head.data = ''
		head.next = None
		return head
	while node:
		if count != k:
			prev = node
			node = node.next
			count += 1
		else:
			prev.next = node.next
			node = node.next
			count = 1
	return head


def deleteK(head, k):
	if k == 1:
		head = None
		return head
	curr = head
	x = k
	while curr and curr.next:
		x -= 1
		if x == 1:
			curr.next = curr.next.next
			x = k
		curr = curr.next
	return head


def deleteK(head, k):
	if k == 1:
		head = None
		return
	count = 1
	temp = head
	while head:
		prev = head
		head = head.next
		count += 1
		if count == k:
			count = 1
			if head is None:
				break
			prev.next = head.next
			head = head.next
	return temp


def deleteK(head, k):
	curr = head
	count = 0
	if k == 1 or head == None:
		return None
	while curr != None and curr.next != None:
		count = count + 1
		if count == k - 1:
			curr.next = curr.next.next
			count = 0
		curr = curr.next
	return head


def deleteK(head, k):
	node = head
	prev = head
	c = 0
	if k == 1:
		return None
	while node:
		nxt = node.next
		if c == k - 1:
			prev.next = nxt
			node.next = None
			node = nxt
			c = 0
		else:
			c = c + 1
			prev = node
			node = nxt
	return head


def deleteK(head, k):
	if k == 1:
		return None
	curr = head
	cn = 1
	while curr and curr.next:
		if cn + 1 == k:
			curr.next = curr.next.next
			cn = 0
		curr = curr.next
		cn += 1
	return head


def deleteK(head, k):
	temp = head
	if k == 0:
		return head
	if k == 1:
		return None
	k = k - 2
	while temp:
		for i in range(k):
			if temp == None:
				break
			temp = temp.next
		if temp == None:
			break
		if temp.next == None:
			break
		else:
			temp.next = temp.next.next
			temp = temp.next
	return head


def deleteK(head, k):
	if k == 0:
		return head
	if k < 2 or not head:
		return None
	A = []
	c = head
	while c:
		A += [c]
		c = c.next
	i = k - 1
	while i < len(A):
		A[i - 1].next = A[i + 1] if i + 1 < len(A) else None
		i += k
	return A[0]


def deleteK(head, k):
	if k == 0:
		return head
	if k == 1:
		return None
	n = 0
	cur = temp = head
	while temp:
		n += 1
		temp = temp.next
	i = 0
	while cur:
		i += 1
		if (i + 1) % k == 0 and cur.next:
			cur.next = cur.next.next
		else:
			cur = cur.next
	return head


def deleteK(head, k):
	if head is None:
		return None
	temp = head
	prev = None
	count = 1
	if k == 1:
		return None
	while temp != None and temp.next != None:
		count += 1
		prev = temp
		temp = temp.next
		if count == k:
			new = temp.next
			del temp
			prev.next = new
			temp = new
			count = 1
	return head


def deleteK(head, k):
	if k == 1:
		return None
	if k == 0:
		return head
	count = 0
	temp = head
	while temp:
		count = count + 1
		temp = temp.next
	x = 1
	ptr = head
	while ptr.next:
		if (x + 1) % k == 0:
			if ptr.next.next:
				ptr.next = ptr.next.next
				x = x + 1
			else:
				ptr.next = None
				break
		x = x + 1
		ptr = ptr.next
	return head


def deleteK(head, k):
	if k == 1:
		return None
	if k == 0:
		return head
	node = head
	index = 1
	while node:
		index = index + 1
		if index % k == 0 and node.next != None:
			node.next = node.next.next
		else:
			node = node.next
	return head


def deleteK(head, k):
	if k == 1:
		return None
	if k == 0:
		return head
	curr = head
	count = 1
	while curr:
		count += 1
		if count % k == 0 and curr.next is not None:
			curr.next = curr.next.next
		else:
			curr = curr.next
	return head


def deleteK(head, k):
	if k == 0:
		return head
	if k == 1:
		return None
	node = head
	prev = head
	while node is not None:
		for i in range(k - 1):
			if node.next is None:
				return head
			prev = node
			node = node.next
		prev.next = node.next
		node = prev.next
	return head


def deleteK(head, k):
	if head == None or k == 0:
		return head
	if k == 1:
		return None
	prev = None
	curr = head
	i = 1
	while curr:
		prev = curr
		curr = curr.next
		i += 1
		if i % k == 0 and prev.next != None:
			prev.next = curr.next
			curr = curr.next
			i += 1
	return head


def deleteK(head, k):
	if head == None or k == 1:
		return
	m = 1
	current = head
	while current and current.next:
		if m == k - 1:
			current.next = current.next.next
			m = 1
			current = current.next
		else:
			m += 1
			current = current.next
	return head


def deleteK(head, k):
	counter = 1
	newhead = head
	if k == 1:
		return None
	while head != None and head.next != None:
		if counter == k - 1:
			head.next = head.next.next
			counter = 0
		head = head.next
		counter += 1
	return newhead


def length(head):
	curr = head
	count = 0
	while curr:
		count += 1
		curr = curr.next
	return count

def deleteK(head, k):
	prev = None
	curr = head
	i = 1
	if k <= 0 or k > length(head):
		return head
	if k == 1:
		return None
	while curr:
		if i % k == 0:
			prev.next = curr.next
		else:
			prev = curr
		curr = curr.next
		i = i + 1
	return head


def deleteK(head, k):
	if k == 0:
		return head
	if k == 1:
		return None
	(prev, nd) = (None, head)
	c = 0
	while nd:
		c += 1
		if c == k:
			prev.next = nd.next
			nd = nd.next
			c = 0
		else:
			prev = nd
			nd = nd.next
	return head