quicksort for linkedlist

quicksort_linkedlist.java

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}

public class linked_list_quicksort {

    public ListNode head;
    public ListNode tail;

    // Constructor function
    public linked_list_quicksort(ListNode head) {
        this.head = head;
        ListNode temp = head;
        while(temp.next != null) temp = temp.next;
        this.tail = temp;
    }

    public  ListNode[] partition(ListNode left, ListNode right) {
        // System.out.println(left.val + " and " + right.val);
        ListNode pivot = left;
        ListNode storeindex = pivot; // the rightmost number (between pivot+1 and right)which is less than pivot
        ListNode track = null; // used to track the previous node of storeindex
        ListNode index = pivot.next;
        while(index != right.next) { // index iterates from left+1 to right
            if(index.val < pivot.val) {
                track = storeindex;
                swap(storeindex.next, index);
                storeindex = storeindex.next;
            }
            index = index.next;
        }

        swap(storeindex, pivot);

        return new ListNode[] {track, storeindex.next};

    }

    public  void sort(ListNode left, ListNode right) {
        if (left != null && right != null && left != right && right.next != left) {
            ListNode[] part = partition(left, right);
            sort(left, part[0]);
            sort(part[1], right);
        }
        return;
    }

    public  void quicksort() {
        sort(head, tail);
    }

    public  void swap (ListNode a, ListNode b) {
        int temp = a.val;
        a.val = b.val;
        b.val = temp;
        return;
    }


    public static void main(String arg[]) {
        ListNode head = new ListNode(3);
        ListNode node2 = new ListNode(5);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(5);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(2);
        ListNode tail = new ListNode(6);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = tail;
        tail.next = null;

        ListNode index = head;
        while(index != null) {
            System.out.print(index.val+ " ");
            index =index.next;
        }
        System.out.println("");

        linked_list_quicksort instance = new linked_list_quicksort(head);
        instance.quicksort();

        index = head;
        while(index != null) {
            System.out.print(index.val+ " ");
            index = index.next;
        }

    }
}