Reverse a Linked List

Write a function reverseLinkedList that takes a head node of a singly linked list, reverses it in place, and returns the new head node.

You will be given the head as the input, and you should return the new head for the reverse linked list which is the current tail node. All the items should be in reverse order, starting with the tail (new head). The reverse should happen in place which means you should not create a new linked list.

Breakdown

Approach and test strategy

Save the forward link before reversing it

Read the approach, boundary cases, and complexity

Retain previous, current, and a saved successor. Before rewriting current.next to previous, save the old successor so the remaining suffix stays reachable. Then advance previous and current. At termination, previous is the new head and the original head is the tail. Reversing stored values is a different operation from relinking the original nodes.

Cases to check

An empty list returns an empty head.
A singleton retains the same node and ends at null.
Trace three nodes and verify their original identities appear in reverse link order.

Cost model

Each node is visited once for O(n) time. Iterative reversal uses O(1) auxiliary references and assumes an acyclic, null-terminated input list.

Programming languages for this lesson

Starter code and reference implementations are available in:

The editor shows which of these languages can run on this deployment.

Follow teacher

Table of Contents

Validate My Answer

You only need to iterate through the list once which means it will be O(n) time.
You will need three pointers to store nodes and no additional data structures. This will be O(1) space.
The solution doesn't use a lot of code, but it does require writing the procedure carefully and in the correct order. Make sure you handle this and think through edge cases.

Follow teacher

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseLinkedList = (head) => {
  // Your solution here
};

Reverse a Linked List

Write a function reverseLinkedList that takes a head node of a singly linked list, reverses it in place, and returns the new head node.

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseLinkedList = (head) => {
  // Your solution here
};