Share my Java solution that uses recursion


  • 1
    X

    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;
            
        }
    }

Log in to reply
 

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