# Solution: Reverse a Linked List

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

**Example:**

The original linked list is as follows:

3 -> 5 -> 2 -> 4The reversed linked list has its arrows changed in direction:

3 <- 5 <- 2 <- 4which means

4 -> 2 -> 5 -> 3

*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.

`3 5 2 4`

**Output:**

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

`4 2 5 3`

# Solution: Reverse a Linked List

# 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

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

# Code

/**

* class Node {

* val: number,

* next: Node,

* }

*//**

* @param {Node} head Head of the linked list.

* @return {Node} Head of the reversed linked list.

*/

function reverseLinkedList(head) {

if (head == null || head.next == null) {

return head;

} const secondNode = head.next;

const reversedTail = reverseLinkedList(secondNode);

secondNode.next = head;

head.next = null; return reversedTail;

}

# 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)**.