Insertion Sort List
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\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 dummy= new ListNode(0);\n        ListNode current=head;\n\n        while(current != null){\n            ListNode prev=dummy;\n            ListNode nextNode=current.next;\n\n        while(prev.next!=null && prev.next.val < current.val){\n            prev=prev.next;\n        }\n\n        current.next=prev.next;\n        prev.next=current;\n        current=nextNode;\n        }\n        return dummy.next;\n    }\n}\n```
['Java']