Skip to content
DSA in JavaScript
Linked Lists, Stacks & Queues

Reversed Linked List Traversal

Algorithm · Starter

Level: StarterIn-Place Reversal

Step through it: In-Place Reversal pattern

1cur
→
2
→
3
→
4

Step 1 of 6

Goal: reverse 1 → 2 → 3 → 4 so it reads 4 → 3 → 2 → 1, without building a new list. We only flip each arrow, using two helpers: prev (the node behind) and cur (the node we are looking at).

The task is to traverse the given linked list in reversed order.

For example for the following linked list:

The order of traversal should be:

37 → 99 → 12

The time complexity is O(n) because we visit every node only once.

Reference

Code

reverseTraversal.js
/**
 * Traversal callback function.
 * @callback traversalCallback
 * @param {*} nodeValue
 */

/**
 * @param {LinkedListNode} node
 * @param {traversalCallback} callback
 */
function reverseTraversalRecursive(node, callback) {
  if (node) {
    reverseTraversalRecursive(node.next, callback);
    callback(node.value);
  }
}

/**
 * @param {LinkedList} linkedList
 * @param {traversalCallback} callback
 */
export default function reverseTraversal(linkedList, callback) {
  reverseTraversalRecursive(linkedList.head, callback);
}

Practice

Spotted a mistake or something unclear? Report it on GitHub.

Linked List Traversal

Algorithm · Starter

Stack

Data Structure · Starter

On this page

ReferenceCode