# Share my Java solution that uses recursion

• I use recursion to solve this problem. Every time when an InsertionSortList(ListNode) is invoked, I assume it will always return an already sorted list. So, at the second step of my implementation, I set head.next to be that already sorted sub list (i.e. every nodes behind head is already in increasing order).

Next, I need to "insert" the head node into this already sorted sub list. Basically I use two pointers currNode and prevNode to keep track of my traversal. My traversal along the sorted sub list will only terminate when I see a value bigger than my head value, or I reach the end of the sub list. Insertion of my head node then takes place. If the while loop is never entered, prevNode will remain as head; in this case, it means there is no need to insert head node into the sub list because the head node is in its right position.

``````public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head==null) return null;
head.next = insertionSortList(head.next);

int headV = head.val;
ListNode currNode = head.next;
ListNode prevNode = head;

while (currNode!=null && currNode.val < headV ){
prevNode = currNode;
currNode = currNode.next;
}

if (prevNode == head) return head;

ListNode newHead = head.next;
prevNode.next = head;
head.next = currNode;

return newHead;

}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.