private HeadTail quickSortUtil(Node head){
        if(head == null || head.next == null){
            HeadTail headTail = new HeadTail();
            headTail.head = head;
            headTail.tail = head;
            return headTail;
        }
        LinkList ll = new LinkList();
        Node leftHead = null;
        Node rightHead = null;
        
        Node curr = head.next;
        head.next = null;
        Node next = null;
        while(curr != null){
            next = curr.next;
            curr.next = null;
            if(curr.data < head.data){
                leftHead = ll.addAtFront(curr, leftHead);
            }else{
                rightHead = ll.addAtFront(curr, rightHead);
            }
            curr = next;
        }
        HeadTail leftSide = quickSortUtil(leftHead);
        HeadTail rightSide = quickSortUtil(rightHead);
        head.next= rightSide.head;
        HeadTail result = new HeadTail();
        result.head = head;
        result.tail = head;
        if(leftSide.tail != null){
            leftSide.tail.next = head;
            result.head = leftSide.head;
        }
        if(rightSide.head != null){
            head.next = rightSide.head;
            result.tail = rightSide.tail;
        }
        return result;
    }
This version keeps tail of each recursion which helps us avoid going to tail in each recursion.
@param head
@return
src/com/interview/linklist/QuickSortSingleLinkList.java