Reverse a linked list

Challenge

Reverse a singly linked list in place by re-pointing each node's next link, using three pointers.

The grader supplies the same node type:

typedef struct node { int data; struct node *next; } node_t;

Task

Implement node_t *reverse(node_t *head) that reverses the list in place and returns the new head (the old tail). No main — the grader calls it.

Input

head: pointer to the first node, or NULL for an empty list.

Output

The head of the reversed list. For an empty list, return NULL.

Example

reverse(1->2->3)   ->   3->2->1
reverse(NULL)      ->   NULL
reverse(7)         ->   7

Edge cases

• Empty list returns NULL.
• A single node is its own reverse.

Rules

• Reverse in place — do not allocate new nodes (use prev/cur/next pointers).

Input format

head: pointer to the first node, or NULL.

Output format

The new head of the reversed list (NULL for an empty list).

Constraints

Reverse in place; allocate no new nodes.

Starter code

node_t *reverse(node_t *head) {
    /* TODO */
    return head;
}