Given a singly linked list, remove all the nodes which have a greater value on their right side.
Example 1:
Input:
LinkedList = 12->15->10->11->5->6->2->3
Output: 15 11 6 3
Explanation: Since, 12, 10, 5 and 2 are
the elements which have greater elements
on the following nodes. So, after deleting
them, the linked list would like be 15,
11, 6, 3.
Example 2:
Input:
LinkedList = 10->20->30->40->50->60
Output: 60
Your Task:
The task is to complete the function compute() which should modify the list as required and return the head of the modified linked list. The printing is done by the driver code,
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ size of linked list ≤ 1000
1 ≤ element of linked list ≤ 1000
Note: Try to solve the problem without using any extra space.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,x):

        self.data=x

        self.next=None



'''

class Solution:

    def compute(self,head):

        #Your code here

Solutions:
class Solution:

	def compute(self, head):
		r_node = self.reverse(head)
		max_val = r_node.data
		prev = r_node
		node = r_node.next
		while node:
			if node.data >= max_val:
				max_val = node.data
				prev = node
			else:
				prev.next = node.next
			node = prev.next
		return self.reverse(r_node)

	def reverse(self, head):
		prev = None
		while head:
			nextt = head.next
			head.next = prev
			prev = head
			head = nextt
		return prev


class Solution:

	def compute(self, head):
		newhead = self.reverse(head)
		p = newhead
		max_so_far = -1
		dummy = Node(0)
		d = dummy
		while p:
			if p.data >= max_so_far:
				max_so_far = p.data
				d.next = p
				d = d.next
			p = p.next
		d.next = None
		result = self.reverse(dummy.next)
		return result

	def reverse(self, head):
		prev = None
		curr = head
		while curr:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		return prev


class Solution:

	def compute(self, head):
		stack = []
		stack.append(head)
		p = head.next
		while p is not None:
			while stack and stack[-1].data < p.data:
				stack.pop()
			stack.append(p)
			p = p.next
		pre = Node(0)
		while stack:
			q = stack.pop()
			q.next = pre.next
			pre.next = q
		return pre.next


class Solution:

	def compute(self, head):

		def reverse(cur):
			prev = None
			while cur:
				next = cur.next
				cur.next = prev
				prev = cur
				cur = next
			return prev
		node = reverse(head)
		mx = 0
		prev = None
		temp = node
		while temp:
			if temp.data < mx:
				prev.next = temp.next
				temp = temp.next
				continue
			prev = temp
			mx = max(mx, temp.data)
			temp = temp.next
		ans = reverse(node)
		return ans


class Solution:

	def compute(self, head):

		def reverse(head):
			curr = head
			prev = None
			nex = None
			while curr != None:
				nex = curr.next
				curr.next = prev
				prev = curr
				curr = nex
			return prev
		head1 = reverse(head)
		prev = head1
		max = head1.data
		curr = head1.next
		while curr != None:
			if curr.data < max:
				prev.next = curr.next
				curr = prev.next
			else:
				max = curr.data
				prev = curr
				curr = curr.next
		head2 = reverse(head1)
		return head2


class Solution:

	def compute(self, head):
		front = head
		prev = None
		while front is not None:
			temp = front.next
			front.next = prev
			prev = front
			front = temp
		max_val = prev.data
		front = prev.next
		head = prev
		while front is not None:
			if max_val > front.data:
				prev.next = front.next
				front = front.next
			else:
				max_val = front.data
				prev = front
				front = front.next
		front = head
		prev = None
		while front is not None:
			temp = front.next
			front.next = prev
			prev = front
			front = temp
		return prev


class Solution:

	def reverse(self, head):
		curr = head
		prev = None
		while curr:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		head = prev
		return head

	def compute(self, head):
		head = self.reverse(head)
		head1 = head
		xy = head1.data
		prev = head1
		curr = head1.next
		while curr:
			if curr.data >= xy:
				xy = curr.data
				prev = curr
			else:
				prev.next = curr.next
			curr = prev.next
		return self.reverse(head1)


class Solution:

	def reverse(self, curr):
		before = None
		temp = curr
		after = temp.next
		while temp:
			after = temp.next
			temp.next = before
			before = temp
			temp = after
		return before

	def compute(self, head):
		head1 = self.reverse(head)
		ma = head1.data
		curr = head1.next
		pre = head1
		while curr:
			if curr.data >= ma:
				ma = curr.data
				pre = curr
				curr = curr.next
			else:
				pre.next = curr.next
				curr = curr.next
		head2 = self.reverse(head1)
		return head2


class Solution:

	def rev(self, head):
		prev = None
		curr = head
		while curr != None:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		head = prev
		return head

	def compute(self, head):
		if head.next == None:
			return head
		head = self.rev(head)
		p = head
		max = head.data
		p = head.next
		q = head
		while p.next != None:
			if p.data >= max:
				q.next = p
				max = p.data
				q = p
			p = p.next
		if p.data < max:
			q.next = None
		else:
			q.next = p
		head = self.rev(head)
		return head


class Solution:

	def compute(self, head):

		def reverseLinkedList(head):
			prev = None
			curr = head
			while curr:
				next_node = curr.next
				curr.next = prev
				prev = curr
				curr = next_node
			return prev
		reversed_head = reverseLinkedList(head)
		prev = None
		curr = reversed_head
		max_value = float('-inf')
		while curr:
			if curr.data >= max_value:
				max_value = curr.data
				prev = curr
				curr = curr.next
			else:
				prev.next = curr.next
				curr = curr.next
		modified_head = reverseLinkedList(reversed_head)
		return modified_head


class Solution:

	def reverse(self, head):
		curr = head
		prev = None
		while curr:
			tmp = curr.next
			curr.next = prev
			prev = curr
			curr = tmp
		head = prev
		return head

	def compute(self, head):
		head = self.reverse(head)
		head1 = head
		mx = head1.data
		prev = head1
		curr = head1.next
		while curr:
			if curr.data >= mx:
				mx = curr.data
				prev = curr
			else:
				prev.next = curr.next
			curr = prev.next
		return self.reverse(head1)


class Solution:

	def revers_singly_link_list(self, head):
		old = head
		new = None
		temp = None
		while old != None:
			temp = old
			old = old.next
			temp.next = new
			new = temp
		return new

	def compute(self, head):
		reversed_head = self.revers_singly_link_list(head)
		c = reversed_head
		new_head = reversed_head
		while c.next != None:
			if int(c.data) > int(c.next.data):
				c.next = c.next.next
			else:
				c = c.next
		return self.revers_singly_link_list(new_head)


class Solution:

	def compute(self, head):
		hd = self.rev(head)
		prev = hd
		mx = prev.data
		curr = hd.next
		while curr:
			if curr.data < mx:
				prev.next = curr.next
			else:
				mx = curr.data
				prev = curr
			curr = prev.next
		hd = self.rev(hd)
		return hd

	def rev(self, hd):
		prev = None
		curr = hd
		while curr:
			tmp = curr.next
			curr.next = prev
			prev = curr
			curr = tmp
		return prev


class Solution:

	def compute(self, head):

		def reverse(head):
			if not head or not head.next:
				return head
			(prev, cur, nxt) = (None, head, head.next)
			while cur:
				cur.next = prev
				prev = cur
				cur = nxt
				nxt = cur.next if cur else None
			return prev
		res = reverse(head)
		ptr = res
		while ptr.next:
			if ptr.next.data >= ptr.data:
				ptr = ptr.next
			else:
				ptr.next = ptr.next.next
		return reverse(res)


class Solution:

	def compute(self, head):
		curr = head
		temp = curr
		while curr.next:
			if curr.data < curr.next.data:
				temp = curr
				temp.data = temp.next.data
				temp.next = temp.next.next
				curr = head
			else:
				curr = curr.next
		return head


class Solution:

	def compute(self, start):
		if start.next is None:
			return start
		prev = None
		curr = start
		while curr:
			forward = curr.next
			curr.next = prev
			prev = curr
			curr = forward
		start = prev
		temp = start
		while temp.next:
			if temp.data > temp.next.data:
				temp.next = temp.next.next
			else:
				temp = temp.next
		if start.next is None:
			return start
		prev = None
		curr = start
		while curr:
			forward = curr.next
			curr.next = prev
			prev = curr
			curr = forward
		start = prev
		return start


class Solution:

	def compute(self, start):
		prev = None
		curr = start
		while curr:
			forw = curr.next
			curr.next = prev
			prev = curr
			curr = forw
		start = prev
		temp = start
		forw = start.next
		while forw:
			if forw.data < temp.data:
				temp.next = forw.next
			else:
				temp = temp.next
			forw = forw.next
		prev = None
		curr = start
		while curr:
			forw = curr.next
			curr.next = prev
			prev = curr
			curr = forw
		start = prev
		return start


class Solution:

	def compute(self, head):
		p = 1
		if head == None or head.next == None:
			return head
		else:
			(t3, temp, t1, t2) = (head, head, head, head.next)
			while t2:
				if t1.data < t2.data:
					if temp == head and p == 1:
						p = 0
						head = t2
						temp = t2
						t1 = t2
						t2 = t2.next
					else:
						temp.next = t2
						(temp, t1, t2) = (head, head, head.next)
						p = 1
				else:
					p = 0
					temp = t1
					t1 = t2
					t2 = t2.next
		return head


class Solution:

	def compute(self, head):
		head = self.reverse(head)
		head1 = head
		curr = head
		maxnode = head
		prev = None
		while curr != None and curr.next != None:
			if curr.next.data < maxnode.data:
				temp = curr.next
				curr.next = temp.next
			else:
				curr = curr.next
				maxnode = curr
		return self.reverse(head)

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


class Solution:

	def reverse(self, head):
		cur = head
		prev = None
		while cur:
			curNext = cur.next
			cur.next = prev
			prev = cur
			cur = curNext
		return prev

	def precalc(self, head):
		cur = head.next
		maxNode = head
		prev = maxNode
		prevTrack = prev
		while cur:
			if cur.data >= maxNode.data:
				prev.next = cur
				prev = cur
				maxNode = cur
			cur = cur.next
		prev.next = None
		return prevTrack

	def compute(self, head):
		head1 = self.reverse(head)
		head2 = self.precalc(head1)
		return self.reverse(head2)


class Solution:

	def compute(self, head):
		if not head or not head.next:
			return head
		prev = None
		curr = head
		while curr:
			next_node = curr.next
			curr.next = prev
			prev = curr
			curr = next_node
		head = prev
		max_node = head
		curr = head.next
		while curr:
			if curr.data < max_node.data:
				max_node.next = curr.next
				curr = curr.next
			else:
				max_node = curr
				curr = curr.next
		prev = None
		curr = head
		while curr:
			next_node = curr.next
			curr.next = prev
			prev = curr
			curr = next_node
		head = prev
		return head


class Solution:

	def compute(self, head):
		flag = True
		while flag:
			n = head
			flag = False
			while n.next is not None:
				if n.data < n.next.data and n == head:
					head = n.next
					flag = True
				elif n.data < n.next.data:
					n.data = n.next.data
					n.next = n.next.next
					flag = True
				n = n.next
				if n is None:
					break
		return head


class Solution:

	def compute(self, head):
		head = self.reverseList(head)
		mini = head.data
		prev = head
		cur = head.next
		while cur is not None:
			nxt = cur.next
			if cur.data < mini:
				prev.next = nxt
				cur.next = None
			else:
				prev = cur
				mini = cur.data
			cur = nxt
		head = self.reverseList(head)
		return head

	def reverseList(self, cur):
		prev = None
		while cur is not None:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt
		return prev


def great_at_right(a):
	ans = [-1] * len(a)
	temp = []
	for i in range(len(a) - 1, -1, -1):
		while temp and temp[-1] <= a[i]:
			temp.pop()
		if temp:
			ans[i] = temp[-1]
		temp.append(a[i])
	return ans

class Solution:

	def compute(self, head):
		temp = []
		curr = head
		while curr:
			temp.append(curr.data)
			curr = curr.next
		ans = great_at_right(temp)
		curr = Node(-1)
		nnode = curr
		for i in range(len(temp)):
			if ans[i] == -1:
				nnode.next = Node(temp[i])
				nnode = nnode.next
		return curr.next


class Solution:

	def compute(self, head):

		def reverse(head):
			itr = head
			prev = None
			right = itr.next
			while right:
				itr.next = prev
				prev = itr
				itr = right
				right = right.next
			itr.next = prev
			return itr
		head = reverse(head)
		itr = head
		max1 = head.data
		prev = head
		itr = head.next
		while itr:
			if itr.data >= max1:
				max1 = itr.data
				prev = itr
				itr = itr.next
			else:
				prev.next = itr.next
				itr = itr.next
		return reverse(head)


class Solution:

	def compute(self, head):
		if head is None or head.next is None:
			return head
		dummy = Node(0)
		dummy.next = head
		prev = dummy
		curr = head
		while curr:
			temp = curr.next
			while temp:
				if curr.data < temp.data:
					prev.next = prev.next.next
					curr = prev.next
					break
				temp = temp.next
			if temp is None:
				prev = curr
				curr = curr.next
		return dummy.next


class Solution:

	def compute(self, head):
		l = []
		itr = head
		while itr:
			l.append(itr.data)
			itr = itr.next
		l.reverse()
		lst = []
		m = l[0]
		for i in range(len(l)):
			if l[i] >= m:
				lst.append(l[i])
				m = l[i]
		lst.reverse()
		head1 = Node(lst[0])
		t = head1
		for i in range(1, len(lst)):
			x = Node(lst[i])
			head1.next = x
			head1 = head1.next
		return t


class Solution:

	def reversing(self, head):
		curr = head
		prev = None
		next1 = head
		while curr != None:
			next1 = curr.next
			curr.next = prev
			prev = curr
			curr = next1
		return prev

	def compute(self, head):
		curr1 = self.reversing(head)
		curr2 = curr1
		while curr2.next != None:
			if curr2.data > curr2.next.data:
				curr2.next = curr2.next.next
			else:
				curr2 = curr2.next
		curr1 = self.reversing(curr1)
		return curr1


def reverse(head):
	pre = None
	while head:
		nxt = head.next
		head.next = pre
		pre = head
		head = nxt
	return pre

class Solution:

	def compute(self, head):
		head = reverse(head)
		maxsofar = head.data
		tmp = head
		while head.next:
			if head.next.data < maxsofar:
				head.next = head.next.next
			else:
				maxsofar = max(maxsofar, head.next.data)
				head = head.next
		head = reverse(tmp)
		return head


class Solution:

	def compute(self, head):
		if head.next == None:
			return head

		def rev(head):
			temp = head
			temp1 = head.next
			head.next = None
			while temp1 != None:
				z = temp1.next
				temp1.next = temp
				temp = temp1
				temp1 = z
			return temp
		root = rev(head)

		def rem(root):
			prev = None
			temp = root
			if root.next == None:
				return
			next = root.next
			l = []
			while temp != None:
				if prev == None:
					prev = root
					temp = temp.next
					l.append(prev)
					continue
				if temp.data < prev.data:
					x = temp.next
					temp.next = None
					prev.next = x
					temp = x
					continue
				prev = temp
				temp = temp.next
			return l[0]
		z = rem(root)
		root = rev(z)
		return root


class Solution:

	def compute(self, head):
		lst = []
		ptr = head
		while ptr:
			lst.append(ptr.data)
			ptr = ptr.next
		ll = LinkedList()
		x = []
		i = len(lst) - 1
		larger = lst[i]
		i -= 1
		while i >= 0:
			if larger <= lst[i]:
				x.append(larger)
				larger = lst[i]
			i -= 1
		x.append(larger)
		y = []
		for i in lst:
			if i > x[-1]:
				y.append(i)
			elif i == x[-1]:
				x.pop()
				y.append(i)
			else:
				continue
		for i in y:
			ll.append(i)
		return ll.head


class Solution:

	def compute(self, head):

		def reverse(node):
			(prev, curr) = (None, node)
			while curr:
				temp = curr.next
				curr.next = prev
				prev = curr
				curr = temp
			return prev
		head = reverse(head)
		maxi = head.data
		prev = head
		dummy = head
		curr = head.next
		while curr:
			if curr.data >= maxi:
				maxi = curr.data
				prev = curr
				curr = curr.next
			else:
				prev.next = curr.next
				curr = prev.next
		dummy = reverse(dummy)
		return dummy


class Solution:

	def compute(self, head):
		dummy = Node(-1)
		dummy.next = head
		back = dummy
		middle = head
		while middle:
			front = middle.next
			found_greater = False
			while front:
				if front.data > middle.data:
					found_greater = True
					break
				front = front.next
			if found_greater:
				back.next = middle.next
			else:
				back = middle
			middle = middle.next
		return dummy.next


class Solution:

	def compute(self, head):
		if not head or not head.next:
			return head
		dummy = head
		curr = head
		while curr:
			temp = curr.next
			while temp:
				if temp.data > curr.data:
					curr.data = temp.data
					curr.next = temp.next
				else:
					temp = temp.next
			curr = curr.next
		return dummy


class Solution:

	def compute(self, head):
		current = head
		prev = None
		while current:
			next_node = current.next
			current.next = prev
			prev = current
			current = next_node
		max_value = prev.data
		current = prev
		while current and current.next:
			if current.next.data < max_value:
				current.next = current.next.next
			else:
				max_value = current.next.data
				current = current.next
		current = prev
		prev = None
		while current:
			next_node = current.next
			current.next = prev
			prev = current
			current = next_node
		return prev


class Solution:

	def compute(self, head):

		def reverseList(head):
			prev = None
			dummy = head
			while dummy:
				next = dummy.next
				dummy.next = prev
				prev = dummy
				dummy = next
			return prev
		head = reverseList(head)

		def do(head):
			t = head
			while head.next:
				if head.next.data < head.data:
					head.next = head.next.next
				else:
					head = head.next
			return t
		t = do(head)
		head = reverseList(t)
		return head


class Solution:

	def compute(self, head):
		curr = head
		prev = None
		temp = None
		while curr:
			if curr.next:
				temp = curr.next
			else:
				temp = None
			curr.next = prev
			prev = curr
			curr = temp
		head = prev
		curr = head
		max_ = 0
		n = None
		while curr:
			if curr.data >= max_:
				if not n:
					n = curr
					head = n
				else:
					n.next = curr
					n = n.next
				max_ = curr.data
			curr = curr.next
		n.next = None
		curr = head
		prev = None
		temp = None
		while curr:
			if curr.next:
				temp = curr.next
			else:
				temp = None
			curr.next = prev
			prev = curr
			curr = temp
		head = prev
		return head


class Solution:

	def compute(self, head):

		def rev(head):
			(curr, prev) = (head, None)
			while curr:
				nxt = curr.next
				curr.next = prev
				prev = curr
				curr = nxt
			return prev
		curr = rev(head)
		maxi = float('-inf')
		newHead = Node(-1)
		temp = newHead
		while curr:
			if curr.data >= maxi:
				maxi = curr.data
				temp.next = Node(maxi)
				temp = temp.next
			curr = curr.next
		return rev(newHead.next)


class Solution:

	def compute(self, head):
		if head is None or head.next is None:
			return head
		head.next = self.compute(head.next)
		if head.next.data > head.data:
			return head.next
		else:
			return head


class Solution:

	def compute(self, head):
		if not head or not head.next:
			return head
		nextNode = self.compute(head.next)
		if nextNode.data > head.data:
			return nextNode
		head.next = nextNode
		return head


class Solution:

	def reverse(self, head):
		if not head:
			return None
		t = head
		while t.next:
			t = t.next
		tail = t
		(head, tail) = (tail, head)
		temp = tail
		after = temp.next
		before = None
		while temp:
			after = temp.next
			temp.next = before
			before = temp
			temp = after
		return head

	def compute(self, head):
		if not head or not head.next:
			return head
		head = self.reverse(head)
		max = head.data
		temp = head
		ans = Node(-1)
		ptr = ans
		while temp:
			if temp.data >= max:
				max = temp.data
				ptr.next = Node(temp.data)
				ptr = ptr.next
			temp = temp.next
		head = self.reverse(ans.next)
		return head


class Solution:

	def compute(self, head):
		if head is None:
			return None
		curr = head
		while curr.next is not None:
			if curr.next.data > curr.data:
				curr.data = curr.next.data
				curr.next = curr.next.next
				curr = head
			else:
				curr = curr.next
		return head


class Solution:

	def compute(self, head):
		if head:
			list1 = []
			list2 = []
			temp = head
			while temp != None:
				list1.append(temp.data)
				temp = temp.next
			max = list1[len(list1) - 1]
			list2.insert(0, max)
			for i in range(len(list1) - 2, -1, -1):
				if max <= list1[i]:
					max = list1[i]
					list2.insert(0, max)
			temp = head
			for i in range(len(list2)):
				temp.data = list2[i]
				if i != len(list2) - 1:
					temp = temp.next
				else:
					temp.next = None
		return head


class Solution:

	def compute(self, head):
		tmp_head = head
		st = []
		while tmp_head:
			if len(st) == 0:
				st.append(tmp_head.data)
				tmp_head = tmp_head.next
			else:
				val = tmp_head.data
				while len(st) > 0 and val > st[-1]:
					st.pop()
				st.append(val)
				tmp_head = tmp_head.next
		new_head = Node(-1)
		tmp = new_head
		for i in range(len(st)):
			new_node = Node(st[i])
			tmp.next = new_node
			tmp = tmp.next
		return new_head.next


class Solution:

	def compute(self, head):
		if head == None or head.next == None:
			return head
		delete_Node = None
		prev = head
		curr = head.next
		while curr != None:
			if prev.data < curr.data:
				if delete_Node == None:
					head = head.next
					prev = head
					curr = head.next
				else:
					delete_Node.next = delete_Node.next.next
					delete_Node = None
					prev = head
					curr = head.next
			else:
				delete_Node = prev
				prev = curr
				curr = curr.next
		return head


from collections import defaultdict

class Solution:

	def compute(self, head):
		head = self.reverse(head)
		curr = head
		max = curr.data
		while curr.next:
			if curr.next.data < max:
				curr.next = curr.next.next
			else:
				max = curr.next.data
				curr = curr.next
		return self.reverse(head)

	def reverse(self, head):
		curr = head
		prev = None
		while curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		return prev


class Solution:

	def compute(self, head):
		b = []
		tmp = head
		while tmp:
			b.append(tmp.data)
			tmp = tmp.next
		tmp = head
		a = []
		m = b[-1]
		j = 0
		for i in reversed(b):
			if i >= m:
				a.append(m)
				m = i
			if j == len(b) - 1:
				a.append(m)
			j += 1
		a.remove(b[-1])
		a = list(reversed(a))
		for i in range(len(a)):
			if i == len(a) - 1:
				tmp.data = a[i]
				tmp.next = None
				return head
			tmp.data = a[i]
			tmp = tmp.next


class Node:

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

def solve(head):
	rev_node = Node(head.data)
	head = head.next
	while head:
		if rev_node.data < head.data:
			rev_node.data = head.data
		else:
			nw_node = Node(head.data)
			nw_node.next = rev_node
			rev_node = nw_node
		head = head.next
	ans_node = Node(rev_node.data)
	rev_node = rev_node.next
	while rev_node:
		if ans_node.data <= rev_node.data:
			nw_node = Node(rev_node.data)
			nw_node.next = ans_node
			ans_node = nw_node
		rev_node = rev_node.next
	return ans_node

class Solution:

	def compute(self, head):
		return solve(head)


class Solution:

	def compute(self, head):
		head = self.reverse(head)
		curr = head.next
		prev = head
		max = head.data
		while curr:
			if max > curr.data:
				prev.next = curr.next
				curr = curr.next
				continue
			max = curr.data
			prev = curr
			curr = curr.next
		return self.reverse(head)

	def reverse(self, head):
		prev = None
		curr = head
		while curr:
			nxt = curr.next
			curr.next = prev
			prev = curr
			curr = nxt
		return prev


class Solution:

	def compute(self, head):
		curr = head
		nextt = None
		prev = None
		while curr != None:
			nextt = curr.next
			curr.next = prev
			prev = curr
			curr = nextt
		head = prev
		current = head
		maxNode = head
		temp = None
		while current is not None and current.next is not None:
			if current.next.data < maxNode.data:
				temp = current.next
				current.next = temp.next
			else:
				current = current.next
				maxNode = current
		curr = head
		prev = None
		while curr is not None:
			nextt = curr.next
			curr.next = prev
			prev = curr
			curr = nextt
		head = prev
		return head


class Solution:

	def compute(self, head):
		new_head = self.reverse_linked_list(head)
		max_value = new_head.data
		curr = new_head
		prev = None
		while curr is not None:
			if curr.data < max_value:
				prev.next = curr.next
				curr = curr.next
				continue
			if curr is not None and curr.data > max_value:
				max_value = curr.data
			prev = curr
			curr = curr.next
		return self.reverse_linked_list(new_head)

	def reverse_linked_list(self, head):
		curr = head
		prev = None
		while curr is not None:
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		return prev


class Solution:

	def compute(self, head):

		def rev(head):
			p = head
			q = head.next
			while q:
				t = q.next
				q.next = p
				p = q
				q = t
			head.next = None
			head = p
			return head
		h_rev = rev(head)
		p = h_rev
		q = p.next
		while q:
			if q.data < p.data:
				t = q.next
				q.next = None
				q = t
				p.next = q
			else:
				p = q
				q = q.next
		h_rev_ans = rev(h_rev)
		return h_rev_ans


class Solution:

	def compute(self, head):

		def reverse(head):
			cur = head
			prev = None
			nxt = None
			while cur != None:
				nxt = cur.next
				cur.next = prev
				prev = cur
				cur = nxt
			head = prev
			return head
		res = reverse(head)
		temp = res
		while res.next != None:
			if res.data > res.next.data:
				res.next = res.next.next
			else:
				res = res.next
		temp1 = reverse(temp)
		return temp1


class Solution:

	def compute(self, head):
		stack = []
		curr = head
		while curr != None:
			stack.append(curr.data)
			curr = curr.next
		temp = [stack[-1]]
		for i in range(len(stack) - 2, -1, -1):
			if temp[-1] <= stack[i]:
				temp.append(stack[i])
		temp = temp[::-1]
		curr = tail = None
		for i in temp:
			new = Node(i)
			if curr is None:
				curr = tail = new
			else:
				tail.next = new
				tail = new
		return curr


class Solution:

	def compute(self, head):
		cur = head
		prev = None
		Next = None
		while cur:
			Next = cur.next
			cur.next = prev
			prev = cur
			cur = Next
		h = prev
		p = h
		n = p.next
		if n != None:
			while n.next:
				if n.data < p.data:
					p.next = n.next
					n.next = None
					n = p.next
				else:
					n = n.next
					p = p.next
			if n.data < p.data:
				p.next = n.next
				n.next = None
				n = p.next
		cur = h
		pr = None
		N = None
		while cur:
			N = cur.next
			cur.next = pr
			pr = cur
			cur = N
		return pr


class Solution:

	def compute(self, head):
		p = head
		q = None
		r = None
		while p:
			r = q
			q = p
			p = p.next
			q.next = r
		new_head = q
		maxdata = q.data
		while q.next:
			if q.next.data >= maxdata:
				maxdata = q.next.data
				q = q.next
			else:
				q.next = q.next.next
		p = new_head
		q1 = None
		r = None
		while p:
			r = q1
			q1 = p
			p = p.next
			q1.next = r
		return q1


class Solution:

	def compute(self, head):

		def reverse(head):
			temp = head
			prev = None
			while temp:
				nxt = temp.next
				temp.next = prev
				prev = temp
				temp = nxt
			return prev

		def sol(head):
			head = reverse(head)
			curr = head
			maxi = head.data
			prev = head
			head = head.next
			while head:
				if head.data >= maxi:
					maxi = head.data
					prev = head
					head = head.next
				else:
					prev.next = head.next
					head = prev.next
			head = reverse(curr)
			return head
		return sol(head)


class Solution:

	def compute(self, head):

		def reverse(head):
			curr = head
			pre = None
			while curr != None:
				next = curr.next
				curr.next = pre
				pre = curr
				curr = next
			return pre
		head = reverse(head)
		node = head
		while node != None:
			while node.next != None and node.data > node.next.data:
				node.next = node.next.next
			node = node.next
		head = reverse(head)
		return head


class Solution:

	def reversing(self, head):
		prev = None
		curr = head
		curr_next = head
		while curr != None:
			curr_next = curr.next
			curr.next = prev
			prev = curr
			curr = curr_next
		head = prev
		return head

	def compute(self, head):
		head = self.reversing(head)
		maxi = head.data
		prev = head
		next1 = head.next
		while next1 != None:
			if prev.data > next1.data:
				prev.next = next1.next
				next1 = prev.next
			else:
				prev = next1
				next1 = next1.next
		head = self.reversing(head)
		return head


class Solution:

	def reverse(self, head):
		if head.next == None:
			return head
		else:
			prev = head
			p = prev.next
			head.next = None
			while prev and p:
				temp = p.next
				p.next = prev
				prev = p
				p = temp
		return prev

	def compute(self, head):
		head = self.reverse(head)
		ma = head.data
		p = head
		while p and p.next:
			if p.next.data < ma:
				temp = p.next
				p.next = temp.next
			else:
				p = p.next
				ma = p.data
		head = self.reverse(head)
		return head


class Solution:

	def compute(self, head):
		l = []
		k = []
		N = 0
		while head:
			N += 1
			l.append(head.data)
			head = head.next
		max = l[N - 1]
		for i in range(len(l) - 1, -1, -1):
			if l[i] >= max:
				max = l[i]
				k.append(max)
		k = k[::-1]
		for j in k:
			print(j, end=' ')


class Solution:

	def compute(self, head):
		head = self.rev(head)
		root = head
		while root.next is not None:
			if root.next.data < root.data:
				root.next = root.next.next
			else:
				root = root.next
		head = self.rev(head)
		return head

	def rev(self, head):
		curr = head
		prev = None
		while curr is not None:
			nex = curr.next
			curr.next = prev
			prev = curr
			curr = nex
		return prev


class Solution:

	def compute(self, head):
		prv = None
		n = head
		while n:
			f = n.next
			n.next = prv
			prv = n
			n = f
		m = prv
		while m.next:
			if m.data > m.next.data:
				m.next = m.next.next
			else:
				m = m.next
		n = prv
		prv1 = None
		while n:
			f = n.next
			n.next = prv1
			prv1 = n
			n = f
		return prv1


class Solution(object):

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


def rev(head):
	if head is None or head.next is None:
		return head
	prev = None
	curr = head
	while curr:
		temp = curr.next
		curr.next = prev
		prev = curr
		curr = temp
	return prev

class Solution:

	def compute(self, head):
		if head is None or head.next is None:
			return head
		rhead = rev(head)
		temp = rhead
		temp_pr = rhead
		max = temp.data
		while temp.next:
			if temp.next.data < max:
				temp.next = temp.next.next
			else:
				max = temp.next.data
				temp = temp.next
		return rev(rhead)


import sys
sys.setrecursionlimit(10001)

class Solution:

	def compute(self, head):

		def deleteFromRight(head):
			if not head:
				return (None, 0)
			(head.next, ele) = deleteFromRight(head.next)
			if ele > head.data:
				return (head.next, ele)
			return (head, head.data)
		(head, _) = deleteFromRight(head)
		return head


class Solution:

	def compute(self, head):

		def rev(s):
			pre = None
			curr = s
			while curr:
				nex = curr.next
				curr.next = pre
				pre = curr
				curr = nex
			return pre
		temp = rev(head)
		start = Node(temp.data)
		pre = start
		temp = temp.next
		while temp:
			if temp.data >= pre.data:
				ne = Node(temp.data)
				pre.next = ne
				pre = ne
			temp = temp.next
		return rev(start)


class Solution:

	def compute(self, head):
		dummy = Node(-1)
		var = dummy
		while head != None:
			curr = head.next
			while curr != None:
				if head.data < curr.data:
					break
				else:
					curr = curr.next
			if curr == None:
				var.next = head
				var = var.next
			head = head.next
		return dummy.next


class Solution:

	def reverse_link_list(self, head):
		current = head
		prev = None
		nxt = None
		while current != None:
			nxt = current.next
			current.next = prev
			prev = current
			current = nxt
		head = prev
		return head

	def compute(self, head):
		head = self.reverse_link_list(head)
		current = head
		store = []
		i = 0
		while current != None:
			if len(store) == 0:
				store.append(current.data)
			elif current.data >= store[i]:
				store.append(current.data)
				i += 1
			current = current.next
		store = store[::-1]
		n = len(store)
		i = 0
		current = head
		while i != n:
			prev = current
			current.data = store[i]
			current = current.next
			i += 1
		prev.next = None
		return head


class Solution:

	def compute(self, head):
		a = []
		cur = head
		while cur:
			a.append(cur.data)
			cur = cur.next
		stack = []
		res = [0] * len(a)
		stack = []
		for i in reversed(range(len(a))):
			cur = a[i]
			while len(stack) != 0 and stack[-1] <= cur:
				stack.pop()
			if len(stack) == 0:
				res[i] = -1
			else:
				res[i] = stack[-1]
			stack.append(cur)
		d = []
		for i in range(len(a)):
			if res[i] == -1:
				d.append(a[i])
		n = Node(0)
		m = n
		for i in d:
			j = Node(i)
			m.next = j
			m = m.next
		return n.next


class Solution:

	def compute(self, head):

		def reverse(head):
			prev = None
			cur = head
			while cur:
				nxt = cur.next
				cur.next = prev
				prev = cur
				cur = nxt
			return prev
		li = reverse(head)
		ptr = li
		cur = li.next
		while cur:
			if ptr.data > cur.data:
				cur = cur.next
				ptr.next = cur
			else:
				ptr = cur
				cur = cur.next
		return reverse(li)


class Solution:

	def reverse(self, head):
		prev = None
		cur = head
		while cur is not None:
			next = cur.next
			cur.next = prev
			prev = cur
			cur = next
		return prev

	def compute(self, head):
		head2 = head
		rev = self.reverse(head)
		temp = rev
		ma = rev.data
		while rev:
			if rev.data >= ma:
				prev = rev
				ma = rev.data
				rev = rev.next
			else:
				prev.next = rev.next
				rev = rev.next
		ans = self.reverse(temp)
		return ans

	def printl(self, node):
		while node:
			print(node.data)
			node = node.next


class Solution:

	def compute(self, head):

		def reverse(pointer):
			p = None
			q = pointer
			while q:
				temp = q.next
				q.next = p
				p = q
				q = temp
			return p
		p = reverse(head)
		q = p
		lst = []
		maxi = p.data
		while p:
			maxi = max(maxi, p.data)
			lst.append(maxi)
			p = p.next
		head = reverse(q)
		i = len(lst) - 1
		p = head
		while head:
			if head.data < lst[i]:
				head = head.next
				i -= 1
			else:
				break
		i -= 1
		q = head
		p = head.next
		while p:
			if p.data < lst[i]:
				temp = p.next
				q.next = p.next
				p = temp
				i -= 1
			else:
				q = p
				p = p.next
				i -= 1
		return head
		return head