Linked List Techniques | Skilled.dev
Learn

Linked List Techniques

Course launching August 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

In this lesson, you learn common techniques and operations with linked lists:

  • Delete a node
  • The runner technique
  • Reverse a linked list
  • Insert an item
  • Recursive iteration

Refer to these techniques as you work on the linked list interview questions.

Execute and visualize these techniques directly in a REPL. We will assume the input for each is a head node using our basic implementation:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Delete a Node

To delete a node, first we find the node that precedes it in the linked list. Then we change this preceding node's next to reference the node after the one we want to delete (precedingNode.next = precedingNode.next.next). Because no items in the linked list point to the node we wanted to delete any longer, it is effectively removed from our linked list, and the garbage collector will recognize this and clear it from memory.

Credit: VisuAlgo
// The input is the index number, and the output will be the head node.
const deleteNode = (head, index) => {
  // If we want to delete the current head node,
  // we just return the node after the current head.
  if (index === 0) {
    return head.next;
  }

  let precedingNode = head;

  // Find the node that precedes the index
  // of the node that we want to delete
  for (let i = 0; i < index - 1; i++) {
    precedingNode = precedingNode.next;
  }

  // Skip past our node to be removed
  // Equivalent to precedingNode.next = precedingNode.next.next
  const nodeToBeRemoved = precedingNode.next;
  precedingNode.next = nodeToBeRemoved.next;

  // There are now no nodes in the linked list that are pointing to nodeToBeRemoved.
  // The node that was before it is now pointing to the one after it.

  return head;
};

let head = new Node(42);
head.next = new Node(9000);
head.next.next = new Node(10);
head.next.next.next = new Node(20);
// 42 -> 9000 -> 10 -> 20

head = deleteNode(head, 2);
// 42 -> 9000 -> 20

head = deleteNode(head, 0);
// 9000 -> 20

The Runner Technique

The runner technique is very commonly used in linked list problems. We use 2 pointers simultaneously to iterate through the linked list instead of just 1. The second pointer either starts before the first pointer, or both pointer start at the same time, and the second pointer jumps multiple nodes instead of touching each one. In either case, the second pointer will reach the end of the linked list faster which provides us additional details to solve a problem.

Let's look at an example of a runner that skips two nodes which means it should reach the end twice as fast as our first pointer:

const runner = head => {
  // We initialize our fast and slow to the head
  let fast = head;
  let slow = head;

  // We iterate through until fast reaches the end
  while (fast != null && fast.next !== null) {
    // We skip to every second node with the fast runner
    fast = fast.next.next;
    slow = slow.next;
  }

  // ... do something with this information
};

Possible use cases:

  • Finding the length of a linked list
  • Determining the midpoint
  • Find an intersection of linked lists
  • Find or remove the kth element from the end
  • Finding cycles in a linked list
  • Finding sub-lists
  • We don't have access to the tail but need the last node

Reverse a Linked List

Developers often joke that the only time they need to understand how to reverse a linked list is for their coding interviews. Regardless, it's a good exercise to solidify your understanding of linked lists, how to traverse them, and how pointers work.

You can reverse a linked list using three pointers that reference the previous node, the current node, and a temporary pointer. You iterate through the list from the head and then direct its next pointer to the previous node until you reach the tail. Then the tail becomes the new head which you return from the function, representing the starting node of our reversed linked list.

const reverseLinkedList = head => {
  let previousNode = null;
  let currentNode = head;

  while (currentNode !== null) {
    // Store the actual next node in the linked list
    const nextNode = currentNode.next;

    // This reverses the current node to point to the previous node
    currentNode.next = previousNode;

    // We now step our previous node forward
    previousNode = currentNode;

    // We step our current node forward
    currentNode = nextNode;
  }

  // Since currentNode becomes null at the tail,
  // we return the previousNode which is new head
  // and the front of our linked list
  return previousNode;
};

Insert an Item

To insert a node into a linked list, it requires O(n) time because we must iterate through the list to the index that we want to insert at. While this isn't incredibly common to use in interviews, it's good to learn for a holistic understanding of linked lists.

Credit: VisuAlgo
const insertNode = (head, index, value) => {
  // Create the node we want to insert
  const insertedNode = new Node(value);
  let precedingNode = head;

  // First check if we want to add a node at the head
  if (index === 0) {
    // Inserting at 0 is equivalent to prepending
    head.prepend(insertedNode);

    return head;
  }

  // Find the node that precedes the index
  // of the node that we want to insert
  for (let i = 0; i < index - 1; i++) {
    precedingNode = precedingNode.next;
  }

  // Store the node that should come after the one we insert
  const nodeAfterInserted = precedingNode.next;

  // Insert our new node at the desired index
  precedingNode.next = insertedNode;

  // Set the inserted node's `next` pointer
  insertedNode.next = nodeAfterInserted;

  return head;
};

let head = new Node(42);
head.next = new Node(9000);
head.next.next = new Node(10);
head.next.next.next = new Node(20);
// 42 -> 9000 -> 10 -> 20

head = insertNode(head, 3, 777);

Recursive Iteration

We have used a while loop to iterate through our linked lists. Anytime we see a while loop, this is a clue that recursion would also work well in this case. Let's see how to iterate a linked list recursively:

const findTailNodeRecursively = node => {
  // Stopping condition when we find the tail node.
  // We know that the `next` will be null for the tail.
  if (node.next === null) {
    return node;
  }

  // Continue call our function recursively with the `next` node.
  return findTailNodeRecursively(node.next);
};

const tailNode = findTailNodeRecursively(head);
Prev
Implement a Linked List
Next
Pointers

Table of Contents