Problem

You are given a reference to a node node inside a doubly linked list (each node has val, prev, next) and an integer val. Insert a new node containing val immediately before node. The list's head may change if node was the head; return the (possibly new) head.

Input / Output

• Input: head, node (a node in the list), integer val.
• Output: head after insertion.

Examples

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

Example 2 Input: 5 <-> 6, node = 5, val = 4 Output: 4 <-> 5 <-> 6 (new head)

Constraints

• 1 <= number of nodes <= 10^5
• node is guaranteed to be in the list.

Approach

Because each node knows its predecessor, no traversal is needed — this is the operation a doubly linked list is built for.

1. p = node.prev.
2. Create new with new.prev = p and new.next = node.
3. node.prev = new.
4. If p is not null, p.next = new; otherwise node was the head, so new becomes the head.
5. Return the head.

Four pointer assignments in a fixed order; drawing the before/after picture prevents the classic mistake of overwriting node.prev before reading it.

Complexity

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

Reference solution (Python)

class DNode:
    def __init__(self, val):
        self.val, self.prev, self.next = val, None, None

def insert_before(head, node, val):
    new = DNode(val)
    p = node.prev
    new.prev, new.next = p, node
    node.prev = new
    if p:
        p.next = new
        return head
    return new

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

Test cases

Input	Expected
1<->3<->4, node=3, val=2	[1,2,3,4]
5<->6, node=5, val=4	[4,5,6]
9, node=9, val=8	[8,9]
backward walk after insert	prev links consistent