Linked List Insert at Position

EasyPython

Problem

YASH Technologies workflow components may need to insert an item at an exact position in an ordered singly linked list. Given the head of a singly linked list, a value, and a zero-based position, insert a new node at that position and return the updated head.

The position may be 0, which inserts the node before the current head, or equal to the current list length, which appends the node. The position is guaranteed to be valid.

Formal Specification

Input: head, a ListNode or None; value, an integer; and position, a zero-based integer.
Output: The head ListNode of the list after insertion.
Each ListNode has integer field val and pointer field next.
Test cases represent linked lists as arrays for readability. The evaluator converts the array into linked nodes before calling the function and converts the result back to an array.

Constraints

0 <= length(head) <= 10^5
0 <= position <= length(head)
-10^9 <= value, node.val <= 10^9
The position is always valid
Use O(1) auxiliary space

Function Signature

def insert_at_position(head, value, position):

The position may be 0, which inserts the node before the current head, or equal to the current list length, which appends the node. The position is guaranteed to be valid.

Formal Specification

Input: head, a ListNode or None; value, an integer; and position, a zero-based integer.
Output: The head ListNode of the list after insertion.
Each ListNode has integer field val and pointer field next.
Test cases represent linked lists as arrays for readability. The evaluator converts the array into linked nodes before calling the function and converts the result back to an array.