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

This page copyright James Fisher 2020. Content is not associated with my employer. Found an error? Edit this page.

Jim Fisher

CV

Speaking

Blogroll

RSS

TigYog

Kickabout