32. Segregate even and odd nodes in a linked list

32. Segregate even and odd nodes in a linked list

Problem link :- click here

package Linked_List;

public class LinkedList__32
{
	
	static Node segregateEvenOdd(LinkedList list)
	{
		LinkedList even = new LinkedList();
		LinkedList odd = new LinkedList();
		
		Node temp = list.head;
		
		while(temp != null)
		{
			if(temp.data % 2 == 0)
			{
				even.push(temp.data);
			}
			else
			{
				odd.push(temp.data);
			}
			
			temp = temp.next;
		}
		
		temp = even.head;
		while(temp.next != null)
			temp = temp.next;
		
		temp.next = odd.head;
		
		return even.head;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(15);
		list.push(8);
		list.push(9);
		list.push(2);
		list.push(4);
		list.push(6);
		
		System.out.println("Linked list : ");
		printList(list);
		
		LinkedList ans = new LinkedList();
		ans.head = segregateEvenOdd(list);
		System.out.println("\nLinked list after segregating : ");
		printList(ans);
	}

	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(n)