5

Delete first occurrence of given Key from a Linked List

 1 year ago
source link: https://www.geeksforgeeks.org/delete-first-occurrence-of-given-key-from-a-linked-list/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Delete first occurrence of given Key from a Linked List

Given a linked list and a key to be deleted. The task is to delete the first occurrence of the given key from the linked list. 

Note: The list may have duplicates.

Examples:  

Input: list = 1->2->3->5->2->10, key = 2
Output: 1->3->5->2->10
Explanation: There are two instances of 2. But as per the question we need to delete the first occurrence only.

Input: list = 3->3->3->3, key = 3
Output: 3->3->3

Approach:

The basic idea is to find the first occurrence of the key by traversing from the head and delete the node. The deletion of a node is explained in detail in Deletion in Linked List.

Follow the steps mentioned below to implement the idea:

  • Start iterating from the given head of the linked list.
  • If the data of the current node matches the given key, this is the first occurrence of the given key.
  • So, delete this node and return the head of the modified linked list.

Below is the implementation of the above approach.

  • Python3
  • Javascript
// A complete working C code to demonstrate
// deletion of given key in singly linked list

#include <stdio.h>
#include <stdlib.h>

// A linked list node
struct Node {
    int data;
    struct Node* next;
};

// Given a reference (pointer to pointer) to the head
// of a list and a value, inserts a new node
// on the front of the list.
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Given a reference (pointer to pointer) to the head
// of a list and a key, deletes the first occurrence
// of key in linked list
void deleteNode(struct Node** head_ref, int key)
{
    // Store head node
    struct Node *temp = *head_ref, *prev;

    // If head node itself holds the key to be deleted
    if (temp != NULL && temp->data == key) {

        // Changed head
        *head_ref = temp->next;
        free(temp);
        return;
    }

    // Search for the key to be deleted, keep track of the
    // previous node as we need to change 'prev->next'
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // If key was not present in linked list
    if (temp == NULL)
        return;

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

    free(temp);
}

// This function prints contents of linked list starting
// from the given node
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

// Driver code
int main()
{
    // Start with the empty list
    struct Node* head = NULL;

    push(&head, 7);
    push(&head, 1);
    push(&head, 3);
    push(&head, 2);

    puts("Created Linked List: ");
    printList(head);
    deleteNode(&head, 1);
    puts("\nLinked List after Deletion of 1: ");
    printList(head);
    return 0;
}
Output
Created Linked List: 
2 3 1 7 
Linked List after Deletion of 1: 
2 3 7

Time Complexity: O(N) where N is the length of the linked list
Auxiliary Space: O(1)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK