Reverse a Linked List

Problem Reverse a singly linked list in place and return the new head. The existing nodes are relinked, not copied.

Input / Output

• Input: head — the first node of a singly linked list.
• Output: the head of the reversed list.

Constraints

• 0 <= n <= 5000 nodes; in place with O(1) extra space (copying values into an array and back is ruled out).
• The list may be empty or hold a single node — both should fall out of the loop without special-casing.

Example

• 1→2→3→4→null → 4→3→2→1→null.
• null → null; 1→null → 1→null.