302. Insert a Node at a Given Position

Given the head of a singly linked list, an integer val, and a 1-based position pos, insert a new node with value val at position pos in the list and return the new head.

Position 1 means inserting at the beginning. If pos is greater than the current length + 1, append to the end.

Input: Head of a singly linked list, integer val, integer pos (1-based).

Output: Head of the updated linked list.

Examples

Input: [1,2,4,5], 3, 3
Output: [1,2,3,4,5]
Explanation: Traverse to position 2 (node before pos=3). Create node(3). Set node(3).next = node(4). Set node(2).next = node(3). Result: 1→2→3→4→5.

Input: [1,2,3], 0, 1
Output: [0,1,2,3]
Explanation: pos=1 means insert at beginning. New node(0) becomes the head.

Input: [1,2,3], 4, 4
Output: [1,2,3,4]
Explanation: pos=4 = length+1. Append at the end. Result: 1→2→3→4.

Constraints

• 0 <= number of existing nodes <= 10^5
• -10^9 <= val <= 10^9
• 1 <= pos <= n+1 (where n is the current length)

Asked by