31. Delete nodes having greater value on right

31. Delete nodes having greater value on right

Problem link :- click here

package Linked_List;

public class LinkedList__31
{
	/*
	 	Given a singly linked list, remove all the nodes which have a greater value on its 
	 	following nodes.
	 			input : 	12  15  10  11  5  6  2  3
	 			output :	15  11    6    3
	 			
	 	we can check the condition if we iterate from last node.
	 	But this is singly linked list we cannot iterate from the last node.
	 	
	 	We can reverse the linked list then we can iterate from the last node.
	 */
	
	static void reverse(LinkedList list)
	{
		Node prev, cur, next;
		prev = null;
		cur = list.head;
		next = cur.next;
		
		while(cur != null)
		{
			next = cur.next;
			
			cur.next = prev;
			
			prev = cur;
			cur = next;
		}
		list.head = prev;
	}
	
	static void compute(LinkedList list)
	{
		reverse(list);
		
		Node temp = list.head;
		Node prev = null;
		int max = list.head.data;
		
		while(temp != null)
		{
			if(temp.data >= max)
				max = temp.data;
			else
			{
				prev.next = temp.next;
			}
			
			prev = temp;
			temp = temp.next;
		}
		
		reverse(list);
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(12);
		list.push(15);
		list.push(10);
		list.push(11);
		list.push(5);
		list.push(6);
		list.push(2);
		list.push(3);
		
		System.out.println("Linked list : ");
		printList(list);
		
		compute(list);
		
		System.out.print("\nLinked list after deleting nodes");
		System.out.println(" having greater value on right");
		printList(list);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)