Solve common data-structure and puzzle problems

Solve the following independent problems (language of your choice; assume typical 32/64-bit constraints): 1) **Reverse a singly linked list** - Given the head of a singly linked list, reverse it and return the new head. (Iterative and/or recursive.) 2) **Numbering on an outward spiral grid** - Integers are written on an infinite 2D grid starting with `1` at `(0,0)`, then `2` at `(1,0)`, and continuing counterclockwise in an outward square spiral (right, up, left, down, ...). - Given integer coordinates `(x, y)`, compute the value written at that cell in **O(1)** time (no simulating the spiral). 3) **100 bulbs toggling** - There are 100 bulbs labeled `1..100`, all initially OFF. - Person 1 toggles every bulb; person 2 toggles bulbs `2,4,6,...`; person 3 toggles `3,6,9,...`; ...; person 100 toggles bulb `100`. - Which bulbs are ON at the end? 4) **Delete a node with only that node** - You are given a pointer/reference to a node `p` inside a singly linked list (you do **not** have the head pointer). - Delete `p` from the list in O(1) time. State any required assumptions. 5) **Bridge-and-torch scheduling** - Four people must cross a bridge with one torch. At most two people cross at a time, and they must carry the torch. - Their individual crossing times are `1, 2, 5, 6` minutes; when two cross together, the pair takes the slower person’s time. - Find a schedule that gets everyone across in **≤ 13 minutes**, or prove it’s impossible. 6) **Validate a BST** - Given the root of a binary tree, determine whether it satisfies the binary search tree property. 7) **Merge intervals** - Given a list of intervals `[start, end]` (inclusive), merge all overlapping intervals and return the merged list. 8) **Maximum adjacent gap after sorting** - Given an unsorted array of integers, if the array were sorted, what is the maximum difference between two adjacent elements in the sorted order? - Design an algorithm better than O(n log n) if possible, and state assumptions.