14. Quick sort on linked list

14. Quick sort on linked list

Problem link :- click here

package Linked_List;

public class LinkedList__14
{

	static Node partition(Node start, Node end)
	{
		if(start==end   ||   start==null   ||  end==null)
			return start;
		
		//iterate is the iterator.
		Node pivot_prev = start;
		Node cur = start;
		Node iterate = start;
		
		int pivot = end.data;
		while(iterate != end)
		{
			if(iterate.data < pivot)
			{
				//then we have to swap the cur and the iterate
				pivot_prev = cur;		//before swapping we should update pivot_prev
				
				int temp = cur.data;
				cur.data = iterate.data;
				iterate.data = temp;
				
				//update the cur
				cur = cur.next;
			}
			
			iterate = iterate.next;
		}
		int temp = cur.data;
		cur.data = end.data;
		end.data = temp;
		
		return pivot_prev;
	}
	
	static void quickSort(Node start, Node end)
	{
		if(start==null  ||  start==end  ||  start==end.next)
			return;
		
		Node pivot_prev = partition(start, end);
		Node pivot = pivot_prev.next;
		
		quickSort(start, pivot_prev);
		quickSort(pivot.next, end);
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(40);
		list.push(20);
		list.push(60);
		list.push(10);
		list.push(50);
		list.push(30);
		
		System.out.println("Linked list before sorting : ");
		printList(list);
		
		Node start = list.head;
		Node end = list.head.next.next.next.next.next;
		quickSort(start, end);
		System.out.println("\nLinked list after sorting : ");
		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^2) in worst case and O(n* log(n)) in average and best case.
Space complexity :- O(1)