Reverse Linked List

Let's start with a classic problem:

Reverse a singly linked list.

One solution is to iterate the nodes in original order and move them to the head of the list one by one. It seems hard to understand. We will first use an example to go through our algorithm.

Algorithm Overview

Let's look at an example:

Keep in mind that the black node 23 is our original head node.

1. First, we move the next node of the black node, which is node 6, to the head of the list:

2. Then we move the next node of the black node, which is node 15, to the head of the list:

3. The next node of the black node now is null. So we stop and return our new head node 15.

More

In this algorithm, each node will be moved exactly once.

Therefore, the time complexity is O(N), where N is the length of the linked list. We only use constant extra space so the space complexity is O(1).