# How to delete a node from the middle of a linked list

Question 2.3 of Cracking the Coding Interview:

Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node. Example:

• Input: the node `c` from the linked list `a->b->c->d->e`
• Output: nothing is returned, but the new linked list looks like `a->b->d->e`

Here’s a diagram of the memory layout that we’re given:

``````            node
|
v
a ---> b ---> c ---> d ---> e
``````

Because we don’t have access to `b`, we can’t free `c`’s memory, as this would cause `b->next` to be a dangling pointer:

``````            node
|
v
a ---> b ~~~>        d ---> e
``````

Therefore, this question is a bit contrived: a sensible API for deleting node `c` would give you access to `b`. But let’s press on.

Instead of freeing `c`’s memory, we’ll have to free a different node’s memory. We have access to `d` via `c->next` … and we know that `d` exists, because the question tells us `c` is somewhere in the middle of the linked list. So, what if we deleted `d` instead?!:

``````            node
|
v
a ---> b ---> c ----------> e
``````

This is wrong, but it would be right if only the value at the third node was `d` instead of `c`! So here’s the idea: overwrite `c`’s contents with `d`’s contents, then remove the node that contained `d`. So we copy the value `d` over:

``````            node   next
|      |
v      v
a ---> b ---> d ---> d ---> e
``````

Then copy `d`’s `next` pointer over:

``````            node   next
|      |
v      v
a ---> b ---> d      d ---> e
|             ^
|             |
+-------------+
``````

Then finally free `d`:

``````            node   next
|      |
v      v
a ---> b ---> d             e
|             ^
|             |
+-------------+
``````

Here’s an implementation in C:

``````#include <stdlib.h>
#include <assert.h>

typedef struct Node {
int val;
struct Node * next;
} Node;

// Precondition: node != NULL && node->next != NULL
void delete_node_middle(Node* node) {
Node* next = node->next;
node->val = next->val;
node->next = next->next;
free(next);
}

Node* mk_node(int val, Node* next) {
Node* node = malloc(sizeof(Node));
node->val = val;
node->next = next;
return node;
}

Node* mk_test_list(int length) {
if (length <= 0) return NULL;
return mk_node(length-1, mk_test_list(length-1));
}

int main(int argc, char** argv) {
// List nodes contain their indexes: 4,3,2,1,0
Node* test_list = mk_test_list(5);

delete_node_middle(test_list->next->next);

assert(test_list->val                   == 4);
assert(test_list->next->val             == 3);
assert(test_list->next->next->val       == 1);
assert(test_list->next->next->next->val == 0);
assert(test_list->next->next->next->next == NULL);

return 0;
}
``````

### More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.