Share my Java solution that uses recursion

  • 1

    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 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;
   = insertionSortList(;
            int headV = head.val;
            ListNode currNode =;
            ListNode prevNode = head;
            while (currNode!=null && currNode.val < headV ){
                prevNode = currNode;
                currNode =;
            if (prevNode == head) return head;
            ListNode newHead =;
   = head;
   = currNode;
            return newHead;

Log in to reply

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