331. Doubly Linked List — Insert at Beginning

Given the head of a doubly linked list and an integer val, insert a new node with value val at the beginning. Update both prev and next pointers correctly. Return the new head.

In a DLL, each node has next (forward) and prev (backward) pointers.

Input: Head of a doubly linked list and integer val.

Output: New head of the doubly linked list (list represented as array).

Examples

Input: [2,3,4,5], 1
Output: [1,2,3,4,5]
Explanation: newNode(1).next=head(2); head(2).prev=newNode(1); return newNode(1).

Input: [10,20], 5
Output: [5,10,20]
Explanation: Prepend 5. Update prev/next pointers.

Input: [], 7
Output: [7]
Explanation: Empty list. New node becomes the only node.

Constraints

• 1<=nodes<=10^4
• -10^9<=Node.val<=10^9

Asked by