Java 34ms solution, clear logic with separate insert method
using insertion sort logic. Insert each new node into a sorted linked list with dummy head.\n \n\n      public class Solution {\n            public ListNode ins
using insertion sort logic. Insert each new node into a sorted linked list with dummy head.\n \n\n      public class Solution {\n            public ListNode insertionSortList(ListNode head) {\n                ListNode sortedHeadDummy = new ListNode(0);\n                ListNode curr = head;\n                while (curr != null) {\n                    ListNode next = curr.next;\n                    insert(sortedHeadDummy, curr);\n                    curr = next;\n                }\n                return sortedHeadDummy.next;\n            }\n            \n            private void insert(ListNode dummyHead, ListNode target) {\n                // left to right scan to insert the target node\n                ListNode curr = dummyHead;\n                while (curr.next != null && curr.next.val < target.val) {\n                    curr = curr.next;\n                }\n                target.next = curr.next;\n                curr.next = target;\n            }\n        }
[]