You are given the head of a doubly Linked List and a Key. Your task is to delete all occurrences of the given key and return the new DLL.
Example:
Input: 
2<->2<->10<->8<->4<->2<->5<->2
2
Output: 
10<->8<->4<->5
Explanation: 
All Occurences of 2 have been deleted.
Your Task:
Complete the function void deleteAllOccurOfX(struct Node** head_ref, int key), which takes the reference of the head pointer and an integer value key. Delete all occurrences of the key from the given DLL.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
0<=Number of Nodes<=10^{4}
-10^{3}<=Node Value <=10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3

'''

# Node Class

	class Node:

	    def __init__(self, data):   # data -> value stored in node

	        self.data = data

	        self.next = None

	        self.prev = None

'''

class Solution:

    #Function to delete all the occurances of a key from the linked list.

    def deleteAllOccurOfX(self, head, x):

        # code here

        # edit the linked list

Solutions:
class Solution:

	def deleteAllOccurOfX(self, head, x):
		while head and head.data == x:
			head = head.next
		if head:
			head.prev = None
			curr = head
			while curr:
				if curr and curr.data == x:
					if curr.prev:
						curr.prev.next = curr.next
					if curr.next:
						curr.next.prev = curr.prev
				curr = curr.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		curr = head
		while curr:
			if curr.data == x:
				if curr.next:
					curr.next.prev = curr.prev
				if not curr.prev:
					head = curr.next
				else:
					curr.prev.next = curr.next
			curr = curr.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		curr = head
		newHead = head
		while curr:
			newCurr = curr.next
			if curr.data == x:
				if curr.prev is None:
					newHead = curr.next
				if curr.prev:
					curr.prev.next = curr.next
				if curr.next:
					curr.next.prev = curr.prev
					(curr.next, curr.prev) = (None, None)
			curr = newCurr
		return newHead


class Solution:

	def deleteAllOccurOfX(self, head, x):
		l = []
		temp = head
		while temp != None:
			l.append(temp.data)
			temp = temp.next
		m = []
		for i in l:
			if i != x:
				m.append(i)
		dummy = Node(None)
		p = dummy
		k = 0
		while k < len(m):
			N = Node(m[k])
			dummy.next = N
			N.prev = dummy
			dummy = dummy.next
			k += 1
		return p.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head or (not head.next and head.data != x):
			return head
		dummy = Node(0)
		dummy.next = head
		head.prev = dummy
		curr = head
		point = dummy
		while curr:
			if curr.data == x:
				temp = curr.next
				point.next = temp
				if temp:
					temp.prev = point
				curr = temp
			else:
				curr = curr.next
				point = point.next
		return dummy.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head:
			return head
		temp = head
		while temp:
			if temp.data == x:
				if temp == head:
					head = head.next
					if head:
						head.prev = None
				elif not temp.next:
					temp.prev.next = temp.next
				else:
					temp.prev.next = temp.next
					temp.next.prev = temp.prev
			temp = temp.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head:
			return None
		newhead = Node(-1)
		newhead.next = head
		head.prev = newhead
		prev = newhead
		p = newhead.next
		while p:
			if p.data == x:
				prev.next = p.next
				if p.next:
					p.next.prev = prev
			else:
				prev = p
			p = p.next
		return newhead.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		while head and head.data == x:
			head = head.next
		temp = head
		r = temp
		while temp:
			if temp.data == x:
				temp.prev.next = temp.next
				if temp.next:
					temp.next.prev = temp.prev
			temp = temp.next
		return r


class Solution:

	def deleteAllOccurOfX(self, head, x):
		curr = head
		while curr is not None:
			if curr.data == x:
				if id(curr) == id(head):
					head = curr.next
					if head is not None:
						head.prev = None
				else:
					if curr.prev:
						curr.prev.next = curr.next
					if curr.next:
						curr.next.prev = curr.prev
			curr = curr.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head:
			return None
		if head.data == key:
			head = head.next
		s = head
		while s:
			if s.data == key:
				if s.next:
					s.next.prev = s.prev
				if s.prev:
					s.prev.next = s.next
			s = s.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		d = Node(-1)
		temp = d
		s = head
		while s:
			if s.data == key:
				s = s.next
			else:
				temp.next = s
				temp = s
				s = s.next
		temp.next = s
		d = d.next
		return d


class Solution:

	def deleteAllOccurOfX(self, head, x):
		p = []
		a = head
		while a is not None:
			if a.data != x:
				p.append(a.data)
			a = a.next
		head1 = None
		b = None
		for i in p:
			m = Node(i)
			if head1 is None:
				head1 = m
				b = head1
			else:
				b.next = m
				m.prev = b
				b = b.next
		return head1


class Solution:

	def deleteAllOccurOfX(self, head, x):
		while head != None and head.data == x:
			head = head.next
		if head == None:
			return head
		else:
			temp = head
		while temp is not None:
			while temp.next != None and temp.next.data == x:
				temp.next = temp.next.next
			else:
				if temp.next == None:
					last = temp
				temp = temp.next
		while last != head:
			while last.prev != None and last.prev.data == x:
				last.prev = last.prev.prev
			else:
				last = last.prev
		return head
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		newhead = dummy = Node(-1)
		dummy.next = head
		while newhead:
			while newhead.next and newhead.next.data == x:
				newhead.next = newhead.next.next
			newhead = newhead.next
		return dummy.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		cur = head
		prev = None
		while cur:
			if cur.data == x:
				if prev:
					prev.next = cur.next
					cur = cur.next
				else:
					head = cur.next
					cur = head
			else:
				prev = cur
				cur = cur.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head:
			return None
		k = Node(data=-1)
		k.next = head
		head.prev = k
		y = k
		while y:
			if y.next and y.next.data == x:
				y.next = y.next.next
			else:
				y = y.next
		return k.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		while head != None and head.data == x:
			head = head.next
		previous = head
		if head != None and head.next != None:
			cur = head.next
		else:
			cur = None
		if cur != None and cur.next != None:
			front = head.next.next
		else:
			front = None
		while front != None:
			if cur.data == x:
				front.prev = previous
				previous.next = front
				cur = front
				front = front.next
			else:
				previous = cur
				cur = front
				front = front.next
		if cur != None and cur.data == x:
			previous.next = front
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if head is None:
			return head
		if head.next is None:
			if head.data == x:
				head = None
			return head
		start = head
		prev = head
		while start != None:
			if start.data == x:
				if start == head:
					start = start.next
					start.prev = None
					prev.next = None
					head = start
				elif start.next != None:
					start = start.next
					prev = prev.prev
					prev.next = start
					start.prev = prev
				else:
					prev = prev.prev
					start.prev = None
					prev.next = None
					start = None
				prev = start
			else:
				start = start.next
				prev = prev.next
		return head


class Solution:

	def deleteNode(self, cur):
		if cur.next is None:
			cur.next = cur.prev
			if cur.prev is not None:
				cur.next.next = None
		else:
			cur.data = cur.next.data
			cur.next = cur.next.next
			if cur.next is not None:
				cur.next.prev = cur

	def deleteAllOccurOfX(self, head, x):
		cur = head
		if cur is None:
			return None
		if cur.next == None and cur.prev == None and (cur.data == x):
			return None
		while cur is not None:
			if cur.data == x:
				self.deleteNode(cur)
			else:
				cur = cur.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		dummy = Node(0)
		prev = dummy
		temp = head
		while temp:
			if temp.data == x:
				temp = temp.next
			else:
				prev.next = temp
				temp.prev = prev
				prev = temp
				temp = temp.next
		prev.next = temp
		return dummy.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if head == None:
			return None
		if head.next == None:
			if head.data == x:
				return None
			else:
				return head
		temp = head
		while temp.next:
			if temp.data == x:
				if temp.prev == None:
					temp = temp.next
					temp.prev = None
				else:
					q = temp.next
					temp = temp.prev
					temp.next = q
					q.prev = temp
			else:
				temp = temp.next
		if temp.data == x:
			temp = temp.prev
			temp.next = None
		while temp.prev:
			temp = temp.prev
		return temp


class Solution:

	def deleteAllOccurOfX(self, head, x):
		cur = head
		nf = ne = of = oe = None
		if head == None:
			return None
		while cur != None:
			if cur.data == x:
				if of == None:
					of = oe = cur
				else:
					oe.next = cur
					cur.prev = oe
					oe = cur
			elif nf == None:
				nf = ne = cur
			else:
				cur.prev = ne
				ne.next = cur
				ne = cur
			cur = cur.next
		if ne != None:
			ne.next = None
		return nf


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if head is None:
			return head
		t = head
		while t:
			if t.data == x:
				if t == head:
					(head, temp) = (head.next, head.next)
				else:
					t.prev.next = t.next
					if t.next:
						t.next.prev = t.prev
				t = t.next
			else:
				t = t.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		ptr = head
		new_head = Node(5)
		n = new_head
		while ptr:
			if ptr.data != x:
				n.next = Node(ptr.data)
				n = n.next
			ptr = ptr.next
		return new_head.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head:
			return head
		dummy = Node(0)
		dummy.next = head
		head.prev = dummy
		curr = head
		while curr:
			if curr.data == key:
				nextNode = curr.next
				if curr.next:
					curr.next.prev = curr.prev
				curr.prev.next = curr.next
				curr = nextNode
			else:
				curr = curr.next
		return dummy.next


class Node:

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

class Solution:

	def deleteAllOccurOfX(self, head, x):
		while head and head.data == x:
			head = head.next
			if head is not None:
				head.prev = None
		curr = head
		while curr and curr.next:
			if curr.next.data == x:
				curr.next = curr.next.next
				if curr.next:
					curr.next.prev = curr
			else:
				curr = curr.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		ans = []
		temp = head
		while temp:
			if temp.data == x:
				temp = temp.next
			else:
				ans.append(temp.data)
				temp = temp.next
		res = LinkedList()
		for i in ans:
			res.push(i)
		return res.head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		temp = head
		new_head = None
		while temp:
			new_temp = temp
			while new_temp and new_temp.data == x:
				new_temp = new_temp.next
			if new_head is None:
				new_head = new_temp
				if new_temp and new_temp != temp:
					prev_copy = new_temp.prev
					prev_copy.next = None
					new_temp.prev = None
				temp = new_temp
				continue
			if new_temp is None:
				prev_copy = temp.prev
				prev_copy.next.prev = None
				prev_copy.next = None
				break
			if new_temp != temp:
				prev_copy = temp.prev
				prev_copy.next = new_temp
				temp.prev = None
				temp.next = None
				new_temp.prev = prev_copy
				temp = new_temp
			else:
				temp = temp.next
		return new_head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		DLL = head
		head = None
		prev = None
		while DLL:
			if DLL.data != x:
				head = DLL
				head.prev = None
				break
			DLL = DLL.next
		DLL = head
		while DLL:
			if DLL.data == x:
				prev.next = DLL.next
				if DLL.next:
					DLL.next.prev = prev
			else:
				prev = DLL
			DLL = DLL.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		p = head
		while p:
			if p == head:
				if p.data == x:
					p = p.next
					head = p
				else:
					p = p.next
			elif p.data == x:
				p.prev.next = p.next
				if p.next:
					p.next.prev = p.prev
					p.prev = None
				p = p.next
			else:
				p = p.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if head == None:
			return Node(-1)
		if head.next == None:
			if head.data == x:
				return Node(-1)
			else:
				return head
		temp = head
		nex = head.next
		while temp:
			if temp == head and temp.data == x:
				head = head.next
				temp.next = None
				nex.prev = None
				temp = nex
				nex = nex.next
			elif temp.next == None and temp.data == x:
				r = temp.prev
				temp.prev = None
				r.next = None
				temp = None
			elif temp.data == x:
				r = temp.prev
				r.next = nex
				nex.prev = r
				temp = nex
				nex = nex.next
			elif temp.next != None:
				temp = nex
				nex = nex.next
			else:
				temp = nex
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		node = head
		isHead = True
		while node:
			if node.data == x:
				if node.next:
					node.next.prev = node.prev
				if node.prev:
					node.prev.next = node.next
				if isHead:
					head = head.next
			else:
				isHead = False
			node = node.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if head is None:
			return head
		while head.data == x:
			head = head.next
			if head is None:
				return head
			else:
				head.prev = None
		curr = head
		while curr:
			if curr.data == x:
				temp_p = curr.prev
				temp_n = curr.next
				if temp_n:
					temp_p.next = temp_n
					temp_n.prev = temp_p
				else:
					temp_p.next = None
			curr = curr.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if head is None:
			return head
		current = head
		while current:
			if current.data == key:
				if current == head:
					head = current.next
					if head is not None:
						head.prev = None
				else:
					current.prev.next = current.next
					if current.next is not None:
						current.next.prev = current.prev
			current = current.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head:
			return None
		while head.data == x and head.next:
			head = head.next
			head.prev = None
		else:
			if head.data == x:
				return None
		head1 = head
		while head.next:
			if head.data == x:
				head.prev.next = head.next
				head.next.prev = head.prev
				head = head.next
			else:
				head = head.next
		else:
			if head.data == x:
				head.prev.next = None
		return head1


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head:
			return None
		dummy = Node(-999999)
		dummy.next = head
		head.prev = dummy
		while head is not None:
			if head.data == x:
				head.prev.next = head.next
				if head.next:
					head.next.prev = head.prev
			head = head.next
		return dummy.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if not head:
			return None
		if head.data == x and (not head.next):
			return None
		if not head.next:
			return head
		s = head
		f = s.next
		ans = Node(123)
		a = ans
		count = 0
		while f:
			if s.data == key:
				s.next = None
				f.prev = None
				s = f
				f = f.next
				if count == 0:
					a.next = s
					count += 1
			elif f.data == key:
				if f.next:
					f.next.prev = s
				s.next = s.next.next
				f = s
				f = f.next
				if count == 0:
					a.next = s
					count += 1
			else:
				if count == 0:
					a.next = s
					count += 1
				f = f.next
				s = s.next
		return ans.next


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if head is None:
			return None
		if head.next is None and head.data == x:
			return None
		if head.next is None and head.data != x:
			return head
		back = None
		curr = head
		forw = curr.next
		while curr is not None:
			if curr.data == x:
				if forw is None:
					back.next = None
					curr = forw
				elif back is None:
					forw.prev = None
					head = forw
					curr = forw
					forw = forw.next
					back = curr.prev
				else:
					back.next = forw
					forw.prev = back
					curr = forw
					forw = forw.next
			elif forw is None:
				curr.next = None
				curr = forw
			else:
				back = curr
				curr = forw
				forw = forw.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		cur = head
		if head == None or (head.next is None and head.data == x):
			return None
		while cur is not None:
			if cur.data == key:
				if cur.prev is not None:
					cur.prev.next = cur.next
				if cur.next is not None:
					cur.next.prev = cur.prev
			elif cur.prev is None:
				head = cur
			cur = cur.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, x):
		if head is None:
			return None
		if head.next is None and head.prev is None:
			return None if head.data == x else head
		ptr = head
		while ptr:
			if ptr.data == x:
				if ptr.next is not None and ptr.prev is not None:
					ptr.next.prev = ptr.prev
					ptr.prev.next = ptr.next
				elif ptr.next is None:
					ptr.prev.next = None
				elif ptr.prev is None:
					head = ptr.next
					ptr.next.prev = None
			ptr = ptr.next
		return head


class Solution:

	def deleteAllOccurOfX(self, head, k):
		head_move = head
		arr = []
		while head_move != None:
			arr.append(head_move.data)
			head_move = head_move.next
		gen_arr = []
		for x in arr:
			if x != k:
				gen_arr.append(x)
		if not gen_arr:
			return
		head_copy = head
		i = 0
		for x in gen_arr:
			head_copy.data = x
			if i != len(gen_arr) - 1:
				head_copy = head_copy.next
			else:
				head_copy.next = None
			i += 1
		return head