quickSort_LinkedList, Java

quickSort_LinkedList

//Title of this code
//'main' method must be in a class 'Rextester'.
//Compiler version 1.7.0_51

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static void main(String args[])
    {
        int[] data={ 8, 3, 10, 1, 2,5,7};
        ListNode pre=new ListNode(0);
        ListNode sewer=pre;
        for (int i=0;i<data.length;i++)
        {
            ListNode cur=new ListNode(data[i]);
            sewer.next=cur;
            sewer=sewer.next;            
        }
        sewer=quickSort(pre.next);
        for (int i=0;i<data.length;i++)
        {
            System.out.println(sewer.val);
            sewer=sewer.next;
        }
        return;
    }
    static class ListNode{
	int val;
	ListNode next=null;
	ListNode(int x) {val=x;};
}

private static ListNode quickSort(ListNode head)
{
	//corner case, alse the exit
	if (head==null||head.next==null)
		return head;
	//partition
	ListNode piv=head;
	ListNode pre1=new ListNode(0);
	ListNode pre2=new ListNode(0);
	ListNode cur1=pre1;
	ListNode cur2=pre2;
	ListNode cur=head.next;
	while (cur!=null)
	{
		if (cur.val<=piv.val)
		{
			cur1.next=cur;
			cur1=cur1.next;
		}
		else
{
	cur2.next=cur;
	cur2=cur2.next;
		}
		cur=cur.next;
	}
	cur1.next=null;
	cur2.next=null;
	//quick sort each sub list
	pre1.next=quickSort(pre1.next);
	pre2.next=quickSort(pre2.next);
	//concaternate them
	cur1=pre1.next;
	while(cur1!=null&&cur1.next!=null)
	{
		cur1=cur1.next;
	}
    if (cur1!=null)
        cur1.next=piv;
    else
        pre1.next=piv;
	piv.next=pre2.next;
	return pre1.next;	
}
}


run \| edit \| history \| help	0