# Solution: Reverse a Linked List

## You’re given a linked list. Write a function to reverse it.

Example:

Don’t create new nodes. Instead, reuse the original linked list, and modify the arrow directions in-place.

Input:
The linked list’s node values, separated by commas.

Output:
The reversed linked list’s node values, separated by commas.

# Observe

A linked list can be split into the head node and the tail, which is also a linked list but headed by the second node.

Insights:
Treat the tail as a linked list, and reverse it by recursively calling the reverse function.

Then, the first node is appended to the reversed tail to construct the entire reversed linked list.

# Algorithm

1. Cover the edge cases of the null and single-element linked list.
2. Get the second node from the original linked list, and recursively reverse the tail.
3. Append the first node to the end of the reversed tail.

# Complexity Analysis

Let N be the length of the linked list.
We visit each node in the linked list once, so the overall complexity is O(N).

Written by