Learn

## Course launching August 2020

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

• Delete a node
• The runner technique
• 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) {
}

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

};

// 42 -> 9000 -> 10 -> 20

// 42 -> 9000 -> 20

// 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

// We iterate through until fast reaches the end
while (fast != null && fast.next !== null) {
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

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;

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

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

}

// 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;

};

// 42 -> 9000 -> 10 -> 20

``````

## 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);
};