Insert Into Linked List

You are given a singly linked list head as well as integers pos and val. Insert a new node with value val before index pos of head.

Constraints

• 1 ≤ n ≤ 100,000 where n is the number of nodes in head
• 0 ≤ pos ≤ n

https://binarysearch.com/problems/Insert-Into-Linked-List

Examples

Example 1

Input

• head =

• pos = 2
• val = 9

Output

• answer =

Example 2

Input

• head =

• pos = 0
• val = 3

Output

• answer =

Example 3

Input

• head =

• pos = 1
• val = 5

Output

• answer =

Solution