Insertion Sort || JAVA Easy Solution
Explanation:\n\n1. Initialization:\n   - A dummy node is created at the beginning to simplify the insertion process. The dummy node\'s next points to the sorted
### Explanation:\n\n1. **Initialization:**\n   - A dummy node is created at the beginning to simplify the insertion process. The dummy node\'s `next` points to the sorted list.\n   - `current` is a pointer initialized to the head of the original linked list.\n\n2. **Iterative Sorting:**\n   - The algorithm iterates through the original linked list (`while(current!=null)`).\n   - Inside the loop:\n      - `next` is used to keep track of the next node in the original list before modification.\n      - The `insert_at_pos` method is called to insert the current node at the correct position in the sorted list.\n\n3. **Insertion at Position:**\n   - The `insert_at_pos` method takes the dummy node and the current node to be inserted.\n   - It traverses the sorted list until it finds the correct position where the current node should be inserted.\n   - The insertion is done by updating the `next` pointers accordingly.\n\n4. **Return:**\n   - The sorted linked list starts from the `dummy.next`, so the method returns `dummy.next`.\n\n### Time Complexity:\n- The outer loop iterates through each node in the original linked list once, making it O(n), where n is the number of nodes.\n- The inner `insert_at_pos` method takes O(n) in the worst case (inserting at the end of the sorted list).\n\nHence, the overall time complexity is O(n^2).\n\n### Space Complexity:\n- The algorithm uses a constant amount of extra space regardless of the input size (dummy node and a few pointers), making it O(1).\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        if(head==null || head.next==null){\n            return head;\n          }\n\n        ListNode dummy=new ListNode(0);\n        ListNode current=head;\n\n        while(current!=null){\n            ListNode next=current.next;\n            insert_at_pos(dummy,current);\n            current=next;\n        }\n      \n      return dummy.next;\n\n    }\n\n    private void insert_at_pos(ListNode dummy,ListNode node){\n        ListNode current=dummy;\n\n        while(current.next!=null && current.next.val<node.val){\n            current=current.next;//move this many numbers to get the proper position\n        }\n\n        node.next=current.next;\n        current.next=node;\n    }\n}\n```
['Linked List', 'Java']