Given a doubly linked list of n nodes sorted by values, the task is to remove duplicate nodes present in the linked list.
Example 1:
Input:
n = 6
1<->1<->1<->2<->3<->4
Output:
1<->2<->3<->4
Explanation:
Only the first occurance of node with value 1 is 
retained, rest nodes with value = 1 are deleted.
Example 2:
Input:
n = 7
1<->2<->2<->3<->3<->4<->4
Output:
1<->2<->3<->4
Explanation:
Only the first occurance of nodes with values 2,3 and 4 are 
retained, rest repeating nodes are deleted.
Your Task:
You have to complete the method removeDuplicates() which takes 1 argument: the head of the linked list.  Your function should return a pointer to a linked list with no duplicate element.
Constraint:
1 <= n <= 10^{5}
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Source: geeksforgeeks | Difficulty: EASY

Starter code: #Back-end complete function Template for Python 3



'''

# 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 remove duplicates from unsorted linked list.

    def removeDuplicates(self, head):

        # code here

        # return head after editing list

Solutions:
class Solution:

	def removeDuplicates(self, head):
		seen = set()
		prev = None
		cur = head
		while cur is not None:
			if cur.data in seen:
				prev.next = cur.next
			else:
				seen.add(cur.data)
				prev = cur
			cur = cur.next
		return head


class Solution:

	def removeDuplicates(self, head):
		curr = head
		while curr and curr.next:
			if curr.data == curr.next.data:
				curr.next = curr.next.next
				if curr.next:
					curr.next.prev = curr
			else:
				curr = curr.next
		return head


class Solution:

	def removeDuplicates(self, head):
		itr = head
		while itr:
			while itr and itr.next and (itr.data == itr.next.data):
				itr.next = itr.next.next
			itr = itr.next
		return head


class Solution:

	def removeDuplicates(self, head):
		l = []
		temp = head
		while temp != None:
			l.append(temp.data)
			temp = temp.next
		l = set(l)
		l = list(l)
		l = sorted(l)
		dummy = Node(None)
		p = dummy
		i = 0
		while i < len(l):
			N = Node(l[i])
			dummy.next = N
			N.prev = dummy
			dummy = dummy.next
			i += 1
		return p.next


class Solution(object):

	def removeDuplicates(self, head):
		curr = prev = head
		while curr:
			if curr.data != prev.data:
				prev.next = curr
				curr.prev = prev
				prev = curr
			curr = curr.next
		prev.next = None
		return head


class Solution(object):

	def removeDuplicates(self, head):
		curr = head
		while curr:
			while curr and curr.next and (curr.data == curr.next.data):
				curr.next = curr.next.next
			curr = curr.next
		return head


class Solution:

	def removeDuplicates(self, head):
		l = []
		t = head
		pre = head
		val = head.data
		while t:
			if t.data != val:
				pre.next = t
				t.prev = pre
				pre = t
				val = t.data
			t = t.next
		pre.next = t
		return head


class Solution:

	def removeDuplicates(self, head):
		temp = head
		r = temp
		while temp.next:
			if temp.data == temp.next.data:
				temp.next = temp.next.next
				if temp.next:
					temp.next.prev = temp
			else:
				temp = temp.next
		return r


class Solution:

	def removeDuplicates(self, head):
		if not head or not head.next:
			return head
		p = head.next
		while p:
			if p.data == p.prev.data:
				p.prev.next = p.next
				if p.next is None:
					break
				p.next.prev = p.prev
				p = p.next
			else:
				p = p.next
		return head


class Solution:

	def removeDuplicates(self, head):
		if head.next is None:
			return head
		temp = head
		while temp and temp.next:
			if temp.data == temp.next.data:
				temp.next = temp.next.next
				if temp.next:
					temp.next.prev = temp
			else:
				temp = temp.next
		return head


class Solution:

	def removeDuplicates(self, head):
		curr = head.next
		while curr is not None:
			if curr.data == curr.prev.data:
				curr.prev.next = curr.next
				if curr.next:
					curr.next.prev = curr.prev
			curr = curr.next
		return head


class Solution:

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


class Solution:

	def removeDuplicates(self, head):
		temp = head
		subhead = head
		while temp is not None:
			while temp.next != None and temp.data == temp.next.data:
				temp = temp.next
			subhead.next = temp.next
			subhead = subhead.next
			temp = subhead
		return head


class Solution:

	def removeDuplicates(self, head):
		a = head
		p = []
		while a is not None:
			p.append(a.data)
			a = a.next
		q = sorted(list(set(p)))
		head1 = None
		b = None
		for i in q:
			m = Node(i)
			if head1 is None:
				head1 = m
				c = head1
			else:
				c.next = m
				m.prev = c
				c = c.next
		return head1


class Solution:

	def removeDuplicates(self, head):
		d = {}
		k = Node(data=-1)
		k.next = head
		h = k
		while h:
			if h.next and h.next.data in d:
				h.next = h.next.next
			else:
				if h.next:
					d[h.next.data] = 1
				h = h.next
		return head


class Solution:

	def removeDuplicates(self, head):
		(pre, cur) = (head, head.next)
		while cur:
			if pre.data != cur.data:
				pre.next = cur
				pre = cur
			cur = cur.next
		pre.next = cur
		return head


class Solution:

	def removeDuplicates(self, head):
		a = head
		b = head.next
		while b != None:
			if a.data == b.data:
				a.next = b.next
				if b.next != None:
					b.next.prev = a
				b = a.next
			else:
				a = a.next
				b = b.next
		return head


class Solution:

	def removeDuplicates(self, head):
		start = head
		prev = None
		count = 0
		while start != None:
			while start.next != None and start.data == start.next.data:
				start = start.next
			start.prev = prev
			if prev is None:
				head = start
				prev = start
			else:
				prev.next = start
				prev = start
			start = start.next
		return head


class Solution:

	def removeDuplicates(self, head):
		left = right = head
		while right:
			if left.data != right.data:
				left.next = right
				right.prev = left
				left = right
			right = right.next
		left.next = None
		return head


class Solution:

	def removeDuplicates(self, head):
		temp = head
		prev = Node(-11)
		while temp:
			if temp.data == prev.data:
				prev.next = temp.next
			else:
				prev = temp
			temp = temp.next
		return head


class Solution:

	def removeDuplicates(self, head):
		hashset = set()
		temp = head
		while temp:
			if temp.data in hashset:
				prev.next = temp.next
			else:
				prev = temp
			hashset.add(temp.data)
			temp = temp.next
		return head


class Solution:

	def removeDuplicates(self, head):
		if head is None or head.next is None:
			return head
		cur = head
		while cur.next is not None:
			if cur.data == cur.next.data:
				cur.next = cur.next.next
			else:
				cur = cur.next
		return head


class Solution:

	def removeDuplicates(self, head):
		l = r = head
		while r:
			if l.data != r.data:
				l.next = r
				r.prev = l
				l = r
			r = r.next
		l.next = None
		return head


class Solution:

	def removeDuplicates(self, head):
		n = p = head
		while n:
			if n.data != p.data:
				p.next = n
				n.prev = p
				p = n
			n = n.next
		p.next = None
		return head


class Node:

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

class Solution:

	def removeDuplicates(self, head):
		dummy = Node(0)
		curr = dummy
		seen = set()
		while head:
			if head.data not in seen:
				seen.add(head.data)
				curr.next = Node(head.data)
				curr = curr.next
			head = head.next
		return dummy.next


class Solution:

	def removeDuplicates(self, head):
		if not head:
			return head
		dummy = Node(0)
		dummy.next = head
		head.prev = dummy
		curr = head
		while curr:
			if curr.data == curr.prev.data:
				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 Solution:

	def removeDuplicates(self, head):
		if head is None:
			return head
		ans = Node(0)
		dummy = ans
		curr = head
		while curr:
			if not curr.prev or curr.prev.data != curr.data:
				ans.next = Node(curr.data)
				ans = ans.next
			curr = curr.next
		return dummy.next


class Solution:

	def removeDuplicates(self, head):
		if head is None:
			return head
		curr = head
		while curr and curr.next:
			if curr.data == curr.next.data:
				curr.next = curr.next.next
			else:
				curr = curr.next
		return head


class Solution:

	def removeDuplicates(self, head):
		temp = head
		while temp:
			new_temp = temp.next
			curr_val = temp.data
			while new_temp and new_temp.data == curr_val:
				new_temp = new_temp.next
			if new_temp == None:
				temp.next = None
				if temp.next:
					temp.next.prev = None
			if new_temp and new_temp.prev != temp:
				if temp.next:
					next_copy = temp.next
					next_copy.prev = None
					temp.next = new_temp
				if new_temp.prev:
					prev_copy = new_temp.prev
					prev_copy.next = None
					new_temp.prev = temp
				temp = new_temp
			else:
				temp = temp.next
		return head


class Solution:

	def removeDuplicates(self, head):
		t1 = head
		t2 = head.next
		while t1 and t2:
			if t1.data == t2.data:
				t2 = t2.next
				t1.next = t2
			else:
				t1 = t1.next
		return head


class Solution:

	def removeDuplicates(self, head):
		temp = head
		while temp != None:
			anchor = temp
			curr = temp
			while curr != None and curr.data == anchor.data:
				curr = curr.next
			anchor.next = curr
			temp = curr
		return head


class Node:

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

class Solution:

	def removeDuplicates(self, head):
		if head is None:
			return head
		current = head
		while current.next is not None:
			if current.data == current.next.data:
				temp = current.next
				current.next = temp.next
				if temp.next is not None:
					temp.next.prev = current
				del temp
			else:
				current = current.next
		return head


class Solution:

	def removeDuplicates(self, head):
		nHead = head
		while head.next:
			if head.data == head.next.data:
				nnext = head.next.next
				head.next = head.next.next
				if nnext:
					nnext.prev = head
			else:
				head = head.next
		return nHead


class Solution:

	def removeDuplicates(self, head):
		current = head
		if not head.next:
			return head
		while current.next.next:
			if current.data == current.next.data:
				p = current.next.next
				current.next = p
				p.prev = current
			else:
				current = current.next
		if current.data == current.next.data:
			current.next = None
		return head


class Solution:

	def removeDuplicates(self, head):
		root = head
		while head.next is not None:
			if head.next.data == head.data:
				head.next = head.next.next
				if head.next:
					head.next.prev = head.next.prev.prev
			else:
				head = head.next
		return root


class Solution:

	def removeDuplicates(self, head):
		if head is None or head.next is None:
			return head
		back = head
		curr = head.next
		forw = curr.next
		while curr is not None:
			if back.data == curr.data:
				if forw is None:
					back.next = None
					curr = forw
				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 removeDuplicates(self, head):
		c = head
		cv = None
		while c is not None:
			if c.data == cv:
				if c.prev is not None:
					c.prev.next = c.next
				if c.next is not None:
					c.next.prev = c.prev
			cv = c.data
			c = c.next
		return head


class Solution:

	def removeDuplicates(self, head):
		if head == None or head.next == None:
			return head
		start = head
		while start and start.next:
			if start.data == start.next.data:
				dummy = start.next
				while dummy.next is not None and start.data == dummy.data:
					dummy = dummy.next
				dummy.prev = start
				start.next = dummy
			start = start.next
		if start.prev.data == start.data:
			start.prev.next = None
		return head


class Solution:

	def removeDuplicates(self, head):
		temp = head
		a = []
		while temp:
			a.append(temp.data)
			temp = temp.next
		b = set(a)
		c = list(b)
		c.sort()
		new = Node(c[0])
		new = head
		for i in c[1:]:
			new.next = Node(i)
			new = new.next
		return head


class Solution:

	def removeDuplicates(self, head):
		temp = head
		while temp:
			sea = temp
			while sea.next and sea.next.data == temp.data:
				sea = sea.next
			temp.next = sea.next
			temp = temp.next
		return head


class Solution:

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


class Solution:

	def removeDuplicates(self, head):
		if head == None or head.next == None:
			return head
		temp = head
		s = set()
		while temp:
			if temp.data not in s:
				s.add(temp.data)
				temp = temp.next
			else:
				if temp.next == None:
					temp = temp.prev
					temp.next = None
					break
				temp.data = temp.next.data
				temp.next = temp.next.next
		return head


class Solution:

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


class Solution:

	def removeDuplicates(self, head):
		a = LinkedList()
		a.append(0)
		while head:
			if a.tail.data != head.data:
				a.append(head.data)
			head = head.next
		a.head = a.head.next
		a.head.prev = None
		return a.head


class Solution:

	def removeDuplicates(self, head):
		if head.next is None:
			return head
		ptr = head
		while ptr.next.next is not None:
			if ptr.data == ptr.next.data:
				b = ptr.next.next
				ptr.next = b
				b.prev = ptr
			else:
				ptr = ptr.next
		ptr1 = head
		while ptr1.next is not None:
			if ptr1.data == ptr1.next.data and ptr1.next.next is None:
				b = ptr.next.next
				ptr.next = b
				break
			if ptr1.data == ptr1.next.data:
				b = ptr1.next.next
				ptr1.next = b
				b.prev = ptr1
			else:
				ptr1 = ptr1.next
		if head.data == head.next.data:
			head = head.next
		return head


class Solution:

	def removeDuplicates(self, head):
		if head == None or head.next == None:
			return head
		curr = head.next
		while curr.next != None:
			if curr.data == curr.next.data:
				pre = curr.prev
				nex = curr.next
				pre.next = nex
				nex.prev = pre
			curr = curr.next
		if head.next == None:
			return head
		else:
			if head.data == head.next.data:
				nex = head.next
				nex.prev = None
				return nex
			return head


class Solution:

	def removeDuplicates(self, head):
		nodes = set()
		curr = head
		while curr:
			if curr.data in nodes:
				if curr.prev:
					curr.prev.next = curr.next
				if curr.next:
					curr.next.prev = curr.prev
			else:
				nodes.add(curr.data)
			curr = curr.next
		return head


class Solution:

	def removeDuplicates(self, head):
		temp = head.next
		ptr = newhead = head
		while temp:
			if temp.data != ptr.data:
				ptr.next = temp
				temp.prev = ptr
				ptr = ptr.next
			temp = temp.next
		ptr.next = None
		return newhead


class Solution:

	def removeDuplicates(self, head):
		temp = head
		while temp.next != None:
			if temp.data == temp.next.data:
				temp.next = temp.next.next
			else:
				temp = temp.next
		return head


class Solution:

	def removeDuplicates(self, head):
		if head.next == None:
			return head
		check = head.data
		p = head.next
		while 1:
			if p.data == check:
				q = p.prev
				q.next = p.next
				if p.next != None:
					p.next.prev = q
			else:
				check = p.data
			p = p.next
			if p == None:
				break
		return head


class Solution:

	def removeDuplicates(self, head):
		if not head or not head.next:
			return head
		curr = head.next
		while curr:
			if curr.prev.data == curr.data:
				curr.prev.next = curr.next
				if curr.next:
					curr.next.prev = curr.prev
			curr = curr.next
		return head


class Solution:

	def removeDuplicates(self, head):
		d = {}
		l = []
		while head:
			if head.data in d.keys():
				d[head.data] += 1
			else:
				d[head.data] = 1
				l.append(head.data)
			head = head.next
		ans = Node(0)
		curr = ans
		for i in l:
			curr.next = Node(i)
			curr = curr.next
		return ans.next


class Solution:

	def removeDuplicates(self, head):
		i = j = head
		v = i.data
		i = i.next
		j = j.next
		while j:
			if v != j.data:
				i.data = j.data
				i = i.next
			v = j.data
			j = j.next
		if i:
			i.prev.next = None
		return head


class Solution:

	def deleteNode(self, node):
		if node.next == None:
			node.prev.next = None
		else:
			if node.next:
				node.next.prev = node.prev
			if node.prev:
				node.prev.next = node.next

	def removeDuplicates(self, head):
		if head == None or head.next == None:
			return head
		curr = head.next
		while curr:
			if curr.data == curr.prev.data:
				self.deleteNode(curr)
			curr = curr.next
		return head


class Solution:

	def removeDuplicates(self, head):
		if head == None:
			return
		dummyNode = Node(-10000)
		dummyNode.next = head
		head.prev = dummyNode
		currNode = head
		while currNode != None and currNode.next != None:
			while currNode.next != None and currNode.data == currNode.next.data:
				dicardNode = currNode.next
				self.removeNode(dicardNode)
			currNode = currNode.next
		return dummyNode.next

	def removeNode(self, node):
		prevNode = node.prev
		nextNode = node.next
		if prevNode != None:
			prevNode.next = node.next
		if nextNode != None:
			nextNode.prev = node.prev
		node.prev = None
		node.next = None
		return


class Solution:

	def removeDuplicates(self, head):
		h = head
		while head.next != None:
			if head.data == head.next.data:
				head.next = head.next.next
				try:
					head.next.next.prev = head
				except:
					a = 1
			else:
				head = head.next
		return h


class Solution:

	def removeDuplicates(self, head):
		fast = head
		slow = head
		while fast != None:
			if fast.data != slow.data:
				slow.next = fast
				fast.prev = slow
				slow = fast
			else:
				fast = fast.next
		slow.next = None
		return head


class Solution:

	def removeDuplicates(self, head):
		l = []
		m = set()
		while head:
			if head.data not in m:
				m.add(head.data)
				l.append(head)
			head = head.next
		n = len(l)
		l[0].prev = None
		for i in range(n - 1):
			l[i].next = l[i + 1]
			l[i + 1].prev = l[i]
		l[n - 1].next = None
		return l[0]


class Solution:

	def removeDuplicates(self, head):
		ptr = head
		while ptr.next:
			if ptr.data == ptr.next.data:
				ptr.next = ptr.next.next
				if ptr.next:
					ptr.next.prev = ptr
				continue
			ptr = ptr.next
		return head


class Solution:

	def removeDuplicates(self, head):
		if not head:
			return head
		if not head.next:
			return head
		(prev, cur, nextt) = (head, head.next, head.next.next)
		while cur and nextt:
			if prev.data == cur.data:
				(prev.next, nextt.prev) = (cur.next, cur.prev)
				(cur, nextt) = (nextt, nextt.next)
			else:
				(prev, cur, nextt) = (cur, nextt, nextt.next)
		if prev.data == cur.data:
			(prev.next, cur.prev) = (None, None)
		return head


class Solution:

	def removeDuplicates(self, head):
		node = head
		while node:
			while node.next and node.data == node.next.data:
				node.next = node.next.next
			node = node.next
		return head