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 lista>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(length1, mk_test_list(length1));
}
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;
}
Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer.