Java / Python with Explanations
For example,\n\nGiven 1 -> 3 -> 2 -> 4 - > null\n\ndummy0 -> 1 -> 3 -> 2 -> 4 - > null\n               |    |\n              ptr toInsert\n-- locate ptr = 3 by 
For example,\n```\nGiven 1 -> 3 -> 2 -> 4 - > null\n\ndummy0 -> 1 -> 3 -> 2 -> 4 - > null\n               |    |\n              ptr toInsert\n-- locate ptr = 3 by (ptr.val > ptr.next.val)\n-- locate toInsert = ptr.next\n\ndummy0 -> 1 -> 3 -> 2 -> 4 - > null\n          |         |\n   toInsertPre     toInsert\n-- locate preInsert = 1 by preInsert.next.val > toInsert.val\n-- insert toInsert between preInsert and preInsert.next\n```\n****\n**Java**\n```\n    public ListNode insertionSortList(ListNode ptr) {    \n        if (ptr == null || ptr.next == null)\n            return ptr;\n        \n        ListNode preInsert, toInsert, dummyHead = new ListNode(0);\n        dummyHead.next = ptr;\n\n        while (ptr != null && ptr.next != null) {\n            if (ptr.val <= ptr.next.val) {\n                ptr = ptr.next;\n            } else {      \n                toInsert = ptr.next;\n                // Locate preInsert.\n                preInsert = dummyHead;\n                while (preInsert.next.val < toInsert.val) {\n                    preInsert = preInsert.next;\n                }\n                ptr.next = toInsert.next;\n                // Insert toInsert after preInsert.\n                toInsert.next = preInsert.next;\n                preInsert.next = toInsert;\n            }\n        }\n        \n        return dummyHead.next;\n    }\n```\n**Python**\n```\n     def insertionSortList(self, head):\n\n        dummyHead = ListNode(0)\n        dummyHead.next = nodeToInsert = head\n        \n        while head and head.next:\n            if head.val > head.next.val:\n                # Locate nodeToInsert.\n                nodeToInsert = head.next\n                # Locate nodeToInsertPre.\n                nodeToInsertPre = dummyHead\n                while nodeToInsertPre.next.val < nodeToInsert.val:\n                    nodeToInsertPre = nodeToInsertPre.next\n                    \n                head.next = nodeToInsert.next\n                # Insert nodeToInsert between nodeToInsertPre and nodeToInsertPre.next.\n                nodeToInsert.next = nodeToInsertPre.next\n                nodeToInsertPre.next = nodeToInsert\n            else:\n                head = head.next\n            \n        return dummyHead.next\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
[]