Delete Fibonacci-Valued Nodes from a Doubly Linked List

Problem Given an integer N and the head and tail of a doubly linked list (DLL), delete every node whose value belongs to the Fibonacci sequence bounded above by N.

Input / Output

• Input: integer N, and head / tail pointers of a DLL of integers.
• Output: the modified DLL (updated head and tail) with all Fibonacci-valued nodes unlinked.

Constraints

• Fibonacci sequence here is 0, 1, 1, 2, 3, 5, 8, 13, 21, ... up to the largest term <= N.
• 0 <= number of nodes <= 10^5; node values are non-negative integers.
• Deletion must be in place — no rebuilding the list from a new array.

Example

• N = 25 → Fibonacci set = {0,1,2,3,5,8,13,21}.
• DLL: head -> 9 <-> 10 <-> 8 <-> 21 <-> 6 <- tail → after removing 8 and 21: head -> 9 <-> 10 <-> 6 <- tail.
• Tricky case: consecutive deletable nodes at the head (1 <-> 2 <-> 9) force both a head reassignment and correct prev fixups on the survivor.