Insert sort on a linked list
Algorithmically, your implementation seems fine. One improvement would be to initialize the sortedList to the first node right away. This necessitates some error checking up front, which I think is better style anyway.

I would also run a check for the current node being the new sorted head first. That way I can automatically assume that I'm inserting after the search position. That allows elimination of the previous variable.

But this is all stylistic stuff to make the logic flow easier to understand. As I said, I think your implementation functions perfectly well.

public static Node insertNode(Node node) {
    if (node == null)
        return null;

    // Make the first node the start of the sorted list.
    Node sortedList = node;
    node = node.next;
    sortedList.next = null;

    while(node != null) {
        // Advance the nodes.
        final Node current = node;
        node = node.next;

        // Find where current belongs.
        if (current.value &lt; sortedList.value) {
            // Current is new sorted head.
            current.next = sortedList;
            sortedList = current;
        } else {
            // Search list for correct position of current.
            Node search = sortedList;
            while(search.next != null &amp;&amp; current.value &gt; search.next.value)
                search = search.next;

            // current goes after search.
            current.next = search.next;
            search.next = current;
        }
    }

    return sortedList;
}


See it run in JavaScript: http://jsfiddle.net/2LDGD/2/