Problem

Given the head of a singly linked list, an integer val and a 1-based position k, insert a new node with value val so that it becomes the k-th node of the list. If k is greater than length + 1, leave the list unchanged. Return the head.

Input / Output

• Input: head, val, k.
• Output: head after insertion.

Examples

Example 1 Input: 1 -> 2 -> 4, val = 3, k = 3 Output: 1 -> 2 -> 3 -> 4

Example 2 Input: 1 -> 2, val = 0, k = 1 Output: 0 -> 1 -> 2

Example 3 Input: 1 -> 2, val = 3, k = 3 Output: 1 -> 2 -> 3

Example 4 Input: 1 -> 2, val = 9, k = 5 Output: 1 -> 2 (unchanged)

Constraints

• 0 <= number of nodes <= 10^5
• 1 <= k <= 10^9

Approach

To insert at position k you need a pointer to node k-1. Use a dummy node before the head so that k = 1 needs no special case:

1. prev = dummy; move it k-1 steps. If prev becomes null before finishing, k is out of range — return head.
2. node.next = prev.next; prev.next = node.
3. Return dummy.next.

The dummy-node pattern is the same one that simplifies deletion, so master it once and reuse it.

Complexity

• Time: O(k)
• Space: O(1)

Reference solution (Python)

def insert_kth(head, val, k):
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(k - 1):
        prev = prev.next
        if prev is None:
            return head
    prev.next = ListNode(val, prev.next)
    return dummy.next

Test cases

Input	Expected
1->2->4, val=3, k=3	[1,2,3,4]
1->2, val=0, k=1	[0,1,2]
1->2, val=3, k=3	[1,2,3]
1->2, val=9, k=5	[1,2]