Problem

Given the head of a singly linked list and an integer val, insert a new node containing val at the beginning of the list and return the new head. The list may be empty.

Input / Output

• Input: head (possibly null), integer val.
• Output: new head.

Examples

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

Example 2 Input: empty, val = 7 Output: 7

Constraints

• 0 <= number of nodes <= 10^5

Approach

1. Create node = ListNode(val).
2. Set node.next = head (works even when head is null).
3. Return node.

No traversal is needed, which is why a linked list is preferred over an array for a stack or a queue's front: pushing to the front is O(1) versus O(n) for shifting array elements.

For a doubly linked list, also set head.prev = node when head exists.

Complexity

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

Reference solution (Python)

class ListNode:
    def __init__(self, val, nxt=None):
        self.val, self.next = val, nxt

def insert_head(head, val):
    return ListNode(val, head)

def to_list(head):
    out = []
    while head:
        out.append(head.val); head = head.next
    return out

Test cases

Input	Expected
2->3->4, val=1	[1,2,3,4]
empty, val=7	[7]
5, val=5	[5,5]
insert 1 then 0 at head	[0,1,...]