Given the head of a singly linked list, a 0-based index and a value val, insert a new node holding val so that it ends up at position index. If index is greater than or equal to the length, append the node at the end. Return the head of the updated list.
Examples
Input: head = 1 -> 2 -> 4, index = 2, val = 3
Output: 1 -> 2 -> 3 -> 4
Input: head = (empty), index = 0, val = 5
Output: 5
Input: head = 1 -> 2, index = 10, val = 9
Output: 1 -> 2 -> 9
Constraints
0 <= number of nodes <= 10**40 <= index <= 10**4- Target: O(index) time, O(1) extra space
Goals
- Create a new ListNode and splice it in
- Use a dummy node so inserting at the front is not a special case