Given a singly linked list, delete middle of the linked list. For example, if given linked list is 1->2->3->4->5 then linked list should be modified to 1->2->4->5.
If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6.
If the input linked list is NULL or has 1 node, then it should return NULL
Example 1:
Input:
LinkedList: 1->2->3->4->5
Output: 1 2 4 5
Example 2:
Input:
LinkedList: 2->4->6->7->5->1
Output: 2 4 6 5 1
Your Task:
The task is to complete the function deleteMid() which should delete the middle element from the linked list and return the head of the modified linked list. If the linked list is empty then it should return NULL.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 <= N <= 1000
1 <= value <= 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Amortized analysis

Starter code: #User function Template for python3

'''
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
'''
def deleteMid(head):
    '''
    head:  head of given linkedList
    return: head of resultant llist
    '''
    
    #code here


Solutions:
def deleteMid(head):
	temp = head
	c = 0
	while temp != None:
		c += 1
		temp = temp.next
	mid = c // 2 - 1
	i = 0
	temp = head
	while i < mid:
		temp = temp.next
		i += 1
	temp.next = temp.next.next
	return head


def deleteMid(head):
	if head.next == None or head == None:
		return None
	elif head.next.next == None:
		head.next = None
	else:
		p = head
		n = 1
		while p.next != None:
			n += 1
			p = p.next
		m = n // 2
		n = 1
		p = head
		while n != m:
			n += 1
			p = p.next
		p.next = p.next.next
	return head


def deleteMid(head):
	slow = head
	fast = head
	prev = None
	while fast and fast.next:
		prev = slow
		slow = slow.next
		fast = fast.next.next
	prev.next = slow.next
	slow = None
	return head


def deleteMid(head):
	temp = head
	size = 0
	while temp != None:
		size += 1
		temp = temp.next
	reach = size // 2
	i = 0
	temp = head
	prev = None
	while temp != None and i < reach:
		i += 1
		prev = temp
		temp = temp.next
	prev.next = temp.next
	return head


def deleteMid(head):
	temp = head
	count = 0
	while temp != None:
		count += 1
		temp = temp.next
	if count % 2 == 0:
		i = 1
		j = count // 2
		temp = head
		prev = None
		while i < j + 1:
			prev = temp
			temp = temp.next
			i += 1
		prev.next = temp.next
	else:
		i = 1
		j = count // 2
		prev = None
		temp = head
		while i <= j:
			prev = temp
			temp = temp.next
			i += 1
		prev.next = temp.next
	return head


def deleteMid(head):
	n = 0
	m = head
	while m != None:
		n += 1
		m = m.next
	a = head
	for i in range(int(n / 2) - 1):
		a = a.next
	a.next = a.next.next
	return head


def deleteMid(head):
	if not head.next:
		return
	slow = head
	fast = head.next.next
	while fast and fast.next:
		fast = fast.next.next
		slow = slow.next
	slow.next = slow.next.next
	return head


def deleteMid(head):
	if head == None or head.next == None:
		return None
	prev = head
	slow = head
	fast = head
	while fast.next != None and fast.next.next != None:
		prev = slow
		slow = slow.next
		fast = fast.next.next
	if fast.next == None:
		prev.next = slow.next
	else:
		slow.next = slow.next.next
	return head


def deleteMid(head):
	if head == None or head.next == None:
		return head
	fast_pointer = head
	prev_of_slow = None
	slow_pointer = head
	while fast_pointer != None and fast_pointer.next != None:
		prev_of_slow = slow_pointer
		slow_pointer = slow_pointer.next
		fast_pointer = fast_pointer.next.next
	prev_of_slow.next = slow_pointer.next
	return head


def deleteMid(head):
	slow = head
	fast = head
	prev = head
	if fast.next is None:
		return None
	while fast and fast.next:
		prev = slow
		slow = slow.next
		fast = fast.next.next
	prev.next = slow.next
	return head


def deleteMid(head):
	length = 0
	dummy = head
	while dummy:
		dummy = dummy.next
		length += 1
	if not head or length == 1:
		return None
	dummy = head
	k = length // 2
	while k - 1 > 0:
		dummy = dummy.next
		k -= 1
	x = dummy.next.next
	dummy.next = x
	return head


def deleteMid(head):
	if head == None:
		return None
	if head.next == None:
		del head
		return None
	temp = head
	cnt = 0
	while temp:
		temp = temp.next
		cnt = cnt + 1
	mid = cnt // 2
	temp = head
	k = 1
	while temp:
		if k == mid:
			temp.next = temp.next.next
		temp = temp.next
		k = k + 1
	return head


def deleteMid(head):
	if head is None or head.next is None:
		return None
	count = 0
	fast = head
	while fast.next is not None:
		count += 1
		fast = fast.next
	fast = head
	mid = count / 2
	loc = 0
	while loc < mid - 1:
		loc += 1
		fast = fast.next
	tempNode = None
	tempNode = fast.next
	if tempNode is None:
		fast.next = None
	else:
		fast.next = tempNode.next
	return head


def deleteMid(head):
	new = head
	i = 1
	while new.next != None:
		i = i + 1
		new = new.next
	i = i // 2
	j = 1
	new = head
	while j < i:
		new = new.next
		j = j + 1
	new.next = new.next.next
	return head


def deleteMid(head):
	temp = head
	count = 0
	while temp:
		count += 1
		temp = temp.next
	temp = head
	count = count // 2
	while count:
		prev = temp
		temp = temp.next
		count -= 1
	prev.next = temp.next
	return head


def deleteMid(head):
	if head == None or head.next == None:
		return None
	else:
		p = head
		q = head
		prev = None
		while q and q.next:
			prev = p
			p = p.next
			q = q.next.next
		if p != None:
			prev.next = p.next
		return head


def getmidprev(head):
	prev = None
	(slow, fast) = (head, head)
	while fast is not None and fast.next is not None:
		prev = slow
		slow = slow.next
		fast = fast.next.next
	return prev

def deleteMid(head):
	midprev = getmidprev(head)
	if midprev is None:
		return None
	midprev.next = midprev.next.next
	return head


def deleteMid(head):
	cur = head
	fast = head
	prev = Node(0)
	h = prev
	prev.next = cur
	while fast and fast.next:
		cur = cur.next
		prev = prev.next
		fast = fast.next.next
	prev.next = cur.next
	return h.next


def deleteMid(head):
	slow = head
	fast = head.next.next
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	slow.next = slow.next.next
	return head


def deleteMid(head):
	if head.next is None:
		return None
	temp = head
	len = 0
	while temp:
		len += 1
		temp = temp.next
	temp = head
	for i in range(len // 2 - 1):
		temp = temp.next
	node2Del = temp.next
	temp.next = temp.next.next
	node2Del.next = None
	return head


def deleteMid(head):
	slow = head
	fast = head.next
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	temp = slow.next
	slow.next = temp.next
	del temp
	return head


def deleteMid(head):
	fast = slow = head
	pre = None
	while fast and fast.next:
		pre = slow
		slow = slow.next
		fast = fast.next.next
	pre.next = pre.next.next
	return head


def deleteMid(head):
	if not head or not head.next:
		return None
	(ptr1, ptr2) = (head, head.next)
	while ptr2 and ptr2.next:
		ptr1 = ptr1.next
		ptr2 = ptr2.next.next if ptr2.next else ptr2.next
	ptr1.data = ptr1.data if ptr2 else ptr1.next.data
	ptr1.next = ptr1.next.next
	return head


def deleteMid(head):
	cur = head
	count = n = 0
	while cur:
		count = count + 1
		cur = cur.next
	if count == 0 or count == 1:
		return NULL
	if count % 2 == 0:
		cur = head
		while n != count / 2 - 1:
			n = n + 1
			cur = cur.next
		temp = cur.next
		cur.next = cur.next.next
		del temp
		return head
	else:
		cur = head
		while n != count // 2 - 1:
			n = n + 1
			cur = cur.next
		temp = cur.next
		cur.next = cur.next.next
		del temp
		return head


class Node:

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

def deleteMid(head):
	if head is None or head.next is None:
		return head
	slow_ptr = head
	fast_ptr = head.next.next
	while fast_ptr is not None and fast_ptr.next is not None:
		slow_ptr = slow_ptr.next
		fast_ptr = fast_ptr.next.next
	temp = slow_ptr.next
	slow_ptr.next = temp.next
	temp = None
	return head


def deleteMid(head):
	if head.next == None:
		return None
	if head.next.next == None:
		head.next = head.next.next
		return head
	fast = head
	slow = head
	while fast.next and fast.next.next:
		fast = fast.next.next
		slow = slow.next
	if fast.next:
		slow = slow.next
	slow.data = slow.next.data
	slow.next = slow.next.next
	return head


def deleteMid(head):
	if head is None or head.next is None:
		return head
	curr = head
	prev = head
	next = None
	while curr != None and curr.next != None:
		curr = curr.next.next
		next = prev
		prev = prev.next
	next.next = prev.next
	return head


def deleteMid(head):
	slow = head
	fast = head
	dummy = Node(-1)
	dummy.next = head
	prev = dummy
	while fast and fast.next:
		prev = slow
		slow = slow.next
		fast = fast.next.next
	prev.next = slow.next
	return dummy.next


def deleteMid(head):
	l = 0
	a = head
	while a != None:
		l += 1
		a = a.next
	mid = l // 2
	l = 0
	prev = None
	cur = head
	front = head.next
	while l < mid:
		l += 1
		prev = cur
		cur = front
		front = front.next
	prev.next = front
	return head


def deleteMid(head):
	p = head
	q = head
	temp = None
	while p and p.next:
		temp = q
		q = q.next
		p = p.next.next
	if temp == None:
		return None
	temp.next = temp.next.next
	return head


def deleteMid(head):
	c = 0
	temp = head
	while temp:
		c += 1
		temp = temp.next
	mid = c // 2
	temp = head
	k = 1
	while temp:
		if k == mid:
			temp.next = temp.next.next
		temp = temp.next
		k += 1
	return head


def deleteMid(head):
	c = 0
	curr = head
	while curr != None:
		c += 1
		curr = curr.next
	curr = head
	for i in range(c // 2 - 1):
		curr = curr.next
	curr.next = curr.next.next
	return head


def deleteMid(head):
	fast = head
	slow = head
	while fast != None and fast.next != None:
		slow = slow.next
		fast = fast.next.next
	mid = slow
	temp = head
	while temp.next != mid:
		temp = temp.next
	val = mid.next
	temp.next = val
	mid = None
	return head


def deleteMid(head):
	start = head
	length = 0
	while start != None:
		length += 1
		start = start.next
	mid = int(length / 2) + 1
	start = 1
	start_node = head
	while start < mid - 1:
		start += 1
		start_node = start_node.next
	start_node.next = start_node.next.next
	return head


def deleteMid(head):
	n = head
	i = 0
	while n is not None:
		i = i + 1
		n = n.next
	x = i // 2
	if i - x == 1:
		head.next = None
	else:
		n = head
		for i in range(0, x):
			n = n.next
		n.data = n.next.data
		n.next = n.next.next
	return head


def deleteMid(head):
	slow = fast = head
	t = None
	while fast and fast.next:
		tmp = slow
		slow = slow.next
		fast = fast.next.next
	tmp.next = slow.next
	return head


def deleteMid(head):
	pre = None
	rabbit = head
	tortoise = head
	while rabbit and rabbit.next:
		pre = tortoise
		rabbit = rabbit.next.next
		tortoise = tortoise.next
	pre.next = tortoise.next
	return head


def deleteMid(head):
	temp = head
	count = 0
	while temp:
		count += 1
		temp = temp.next
	temp = head
	for i in range(count // 2 - 1):
		temp = temp.next
	temp.next = temp.next.next
	return head


def deleteMid(head):
	temp = head
	count = 0
	while temp != None:
		count += 1
		temp = temp.next
	temp = head
	count = count // 2
	while count - 1:
		temp = temp.next
		count -= 1
	temp.next = temp.next.next
	return head


def deleteMid(head):
	if head is None:
		return head
	if head.next is None:
		return None
	fast = slow = head
	pre = None
	while fast and fast.next:
		fast = fast.next.next
		pre = slow
		slow = slow.next
	if pre is not None:
		pre.next = slow.next
	return head


def deleteMid(head):
	count = 0
	temp = head
	if head == None:
		return head
	if head.next == None:
		return None
	while temp:
		count += 1
		temp = temp.next
	mid = count // 2
	st = head
	while mid > 1:
		st = st.next
		mid = mid - 1
	temp = st.next
	st.next = st.next.next
	del temp
	return head


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


def deleteMid(head):
	if head is None:
		return None
	temp = head
	temp2 = head
	count = 0
	while temp is not None:
		count = count + 1
		temp = temp.next
	i = 1
	while i < count // 2:
		i = i + 1
		temp2 = temp2.next
	temp_next = temp2.next
	temp2.next = temp_next.next
	temp_next.next = None
	return head


def deleteMid(head):
	p = head
	c1 = 0
	c2 = 0
	while p:
		c1 = c1 + 1
		p = p.next
	c3 = c1 // 2 + 1
	if c3 <= 1:
		return None
	p = head
	q = None
	while p:
		c2 = c2 + 1
		if c2 == c3:
			q.next = p.next
		q = p
		p = p.next
	return head


def deleteMid(head):
	temp = head
	if head == None:
		return head
	c = 0
	while temp != None:
		c += 1
		temp = temp.next
	d = int(c / 2)
	temp = head
	for i in range(d - 1):
		temp = temp.next
	temp.next = temp.next.next
	return head


def deleteMid(head):
	fast = head
	slow = head
	tail = None
	while fast != None and fast.next != None:
		tail = slow
		slow = slow.next
		fast = fast.next.next
	tail.next = slow.next
	del slow
	return head


def deleteMid(head):
	if head == None:
		return None
	if head.next == None:
		del head
		return None
	(temp, count) = (head, 0)
	while temp:
		temp = temp.next
		count += 1
	m = count // 2
	(temp, k) = (head, 1)
	while temp:
		if k == m:
			temp.next = temp.next.next
		temp = temp.next
		k += 1
	return head


def deleteMid(head):
	slow = head
	fast = head
	new = head
	while fast.next and fast.next.next:
		slow = slow.next
		fast = fast.next.next
	if fast.next:
		if fast.next.next == None:
			slow.next = slow.next.next
	else:
		while new.next != slow:
			new = new.next
		new.next = new.next.next
	return head


def deleteMid(head):
	slow = head
	fast = head
	prev = Node(0)
	while fast != None and fast.next != None:
		prev = slow
		slow = slow.next
		fast = fast.next.next
	prev.next = prev.next.next
	return head


def deleteMid(head):
	cur = head
	ans = []
	while cur:
		ans.append(cur.data)
		cur = cur.next
	ind = len(ans) // 2
	ans.pop(ind)
	l = Node(0)
	h = l
	for i in ans:
		n = Node(i)
		l.next = n
		l = l.next
	return h.next


def deleteMid(head):
	temp = head
	r = head
	count = 0
	while temp is not None:
		temp = temp.next
		count += 1
	for i in range(count // 2 - 1):
		head = head.next
	head.next = head.next.next
	return r


def deleteMid(head):
	c = a = b = head
	b = b.next.next
	while b and b.next:
		a = a.next
		b = b.next.next
	a.next = a.next.next
	return c


def deleteMid(head):
	i = 0
	t = head
	while t:
		t = t.next
		i += 1
	t1 = head
	for j in range(i):
		if j == i // 2 - 1:
			t1.next = t1.next.next
			break
		t1 = t1.next
	return head


def deleteMid(head):
	slow = head
	fast = head
	ptr = None
	if head == None:
		return None
	while fast and fast.next:
		ptr = slow
		slow = slow.next
		fast = fast.next.next
	ptr.next = slow.next
	slow.next = None
	return head


def deleteMid(head):
	count = 0
	curr = head
	while curr is not None:
		count += 1
		curr = curr.next
	if count <= 1:
		return None
	nodeToDel = count // 2 + 1
	cnt = 0
	curr = head
	while cnt < nodeToDel - 2:
		cnt += 1
		curr = curr.next
	curr.next = curr.next.next
	return head


def deleteMid(head):
	lst = []
	while head:
		lst.append(head.data)
		head = head.next
	del lst[len(lst) // 2]
	a = Node(0)
	temp = a
	for i in lst:
		temp.next = Node(i)
		temp = temp.next
	return a.next


def deleteMid(head):
	if head == None or head.next == None:
		return None
	temp = head
	length = 0
	while temp != None:
		length += 1
		temp = temp.next
	length = length // 2
	i = 0
	temp = head
	prev = None
	while i < length:
		prev = temp
		temp = temp.next
		i += 1
	prev.next = temp.next
	temp.next = None
	return head


def deleteMid(head):
	c = length(head)
	mid = c // 2
	itr = head
	i = 0
	while itr:
		if mid - 1 == i:
			itr.next = itr.next.next
		i += 1
		itr = itr.next
	return head

def length(head):
	c = 0
	itr = head
	while itr:
		c += 1
		itr = itr.next
	return c


def deleteMid(head):
	if head == None:
		return None
	if head.next == None:
		del head
		return None
	c = 0
	t = head
	while t:
		c += 1
		t = t.next
	mid = c // 2
	t = head
	k = 1
	while t:
		if k == mid:
			t.next = t.next.next
		t = t.next
		k += 1
	return head


def deleteMid(head):
	fast = slow = head
	while fast and fast.next:
		fast = fast.next.next
		slow = slow.next
	curr = head
	while curr.next != slow:
		curr = curr.next
	if slow.next is None:
		curr.next = None
	else:
		curr.next = slow.next
	return head


import math

def deleteMid(head):
	count = 1
	temp = head
	while temp.next:
		count += 1
		temp = temp.next
	n = math.floor(count / 2)
	temp1 = head
	i = 0
	while i < n - 1:
		temp1 = temp1.next
		i += 1
	temp1.next = temp1.next.next
	return head


def deleteMid(head):
	if head is None:
		return head
	if head.next is None:
		return Null
	temp = head
	c = 0
	while temp:
		c += 1
		temp = temp.next
	b = c // 2
	temp = head
	i = 1
	while temp:
		if i == b:
			temp.next = temp.next.next
		temp = temp.next
		i += 1
	return head


def deleteMid(head):
	stack = [head]
	count = 0
	while len(stack) > 0:
		current = stack.pop()
		count += 1
		if current.next:
			stack.append(current.next)
	if count > 1:
		stack.append(head)
		for i in range(count // 2 - 1):
			current = stack.pop()
			stack.append(current.next)
		current = stack.pop()
		current.next = current.next.next
		return head
	else:
		return None


def deleteMid(head):
	temp = head
	length = 1
	while temp.next:
		temp = temp.next
		length += 1
	mid = length // 2
	temp = head
	k = 1
	while temp:
		if k == mid:
			temp.next = temp.next.next
		temp = temp.next
		k += 1
	return head


def deleteMid(head):
	ans = Node(123)
	p = ans
	p.next = head
	s = head
	f = head.next
	while f and f.next:
		f = f.next.next
		s = s.next
		p = p.next
	if f:
		s.next = s.next.next
		return ans.next
	elif not f:
		p.next = p.next.next
		return ans.next


def deleteMid(head):
	dummy = Node(0)
	dummy.next = head
	(slow, fast) = (dummy, head)
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	slow.next = slow.next.next
	return dummy.next


def deleteMid(head):
	slow = head
	fast = head
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	mid = slow
	temp = head
	while temp.next != mid:
		temp = temp.next
	temp.next = mid.next
	return head