Write a function that deletes the n th element from a linked list. If the linked

Question

Write a function that deletes the nth element from a linked list. If the linked list doesn't even have n nodes, don't delete any of them. The function signature is: node *deleteNth(node *head, int n). Try implementing the function iteratively and recursively. (In terms of how to interpret n, you can start counting your nodes from zero or one; your choice.)

I gave it a shot on the iterative version but I'm not getting it. I have no idea where to start on the recursive version. Help

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

typedef struct node

{

int data;

struct node *next;

} node;

node *create_node(int data)

{

node *new_node = malloc(sizeof(node));

if (new_node == NULL)

{

fprintf(stderr, "Error: Out of memory in create_node() ");

exit(1);

}

new_node->data = data;

new_node->next = NULL;

return new_node;

}

node *tail_insert(node *head, int data)

{

node *temp = head;

if (head == NULL)

return create_node(data);

while (temp->next != NULL)

temp = temp->next;

temp->next = create_node(data);

return head;

}

void print_list(node *head)

{

if (head == NULL)

{

printf("(empty list) ");

return;

}

printf("List = ");

while (head != NULL)

{

printf("%d%c", head->data, (head->next == NULL) ? ' ' : ' ');

head = head->next;

}

}

node *deleteNth(node *head, int n)

{

int i;

node *temp = head;

if (head == NULL)

return NULL;

if (n == 0)

{

head = temp->next;

free(temp);

return head;

}

// Find previous node of the node to be deleted

for (i = 0; temp != NULL && i < n - 1; i++)

temp = temp->next;

// If position is more than number of nodes

if (temp == NULL || temp->next == NULL)

return head;

// Node temp->next is the node to be deleted

// Store pointer to the next of node to be deleted

node *next = temp->next->next;

// Unlink the node from linked list

free(temp->next); // Free memory

temp->next = next; // Unlink the deleted node from list

return head;

}

int main(void)

{

int i;

node *head = NULL, *tail = NULL;

int a[] = {1, 5, 7, 8, 4, 12, 2};

srand((unsigned int)time(NULL));

for (i = 0; i < 7; i++)

{

tail = tail_insert(tail, a[i]);

if (head == NULL)

head = tail;

}

print_list(head);

head = deleteNth(head, 6);

print_list(head);

printf(" ");

return 0;

}

Explanation / Answer

Please find my answer.

Iterative:

node* deleteNth(node *head, int position)
{
// If linked list is empty
if (head == NULL)
return NULL;

// Store head node
node* temp = head;

// If head needs to be removed
if (position == 0)
{
temp = temp->next; // Change head
free(head); // free old head
return temp;
}

// Find previous node of the node to be deleted
for (int i=0; temp!=NULL && i<position-1; i++)
temp = temp->next;

// If position is more than number of ndoes
if (temp == NULL || temp->next == NULL)
return head;

// node temp->next is the node to be deleted
// Store pointer to the next of node to be deleted
node *next = temp->next->next;

// Unlink the node from linked list
free(temp->next); // Free memory

temp->next = next; // Unlink the deleted node from list
return head;
}

Recursive:

// Deletes k-th node and returns new header.
node* deleteNode(node* start, int k)
{
// If invalid k
if (k < 1)
return start;

// If linked list is empty
if (start == NULL)
return NULL;
  
// Base case (start needs to be deleted)
if (k == 1)
{
node *res = start->next;
free(start);
return res;  
}

start->next = deleteNode(start->next, k-1);
return start;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.