Simple Java Solution True Insertion Sort
Intuition\nSplit into two lists. Take from unsorted list and insert into sorted list.\n\n# Approach\nSame as intuition \xAF\\(\u30C4)/\xAF\n\n# Complexity\n- Ti
# Intuition\nSplit into two lists. Take from unsorted list and insert into sorted list.\n\n# Approach\nSame as intuition \xAF\\\\_(\u30C4)_/\xAF\n\n# Complexity\n- Time complexity: O(n^2)\n\n# Code\n```\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     int val;\n *     ListNode next;\n *     ListNode() {}\n *     ListNode(int val) { this.val = val; }\n *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n * }\n */\nclass Solution {\n    public ListNode insertionSortList(ListNode head) {\n        ListNode curr = head.next;\n        ListNode h = head; \n        h.next = null;\n        while (curr != null) {\n            ListNode temp = curr;\n            curr = curr.next;\n            ListNode px = null;\n            ListNode x = h;\n            while (x != null && x.val < temp.val) {\n                px = x;\n                x = x.next;\n            }\n            if (px != null) \n                px.next = temp;\n            else \n                h = temp;\n            temp.next = x;\n        }\n        return h;\n    }\n}\n```
['Java']