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 -> 4
The reversed linked list has its arrows changed in direction:
3 <- 5 <- 2 <- 4
which 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

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.

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