{"id":5288,"date":"2021-09-27T19:40:22","date_gmt":"2021-09-27T19:40:22","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=5288"},"modified":"2022-03-10T19:42:20","modified_gmt":"2022-03-10T19:42:20","slug":"linked-list-deleting-node","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/linked-list-deleting-node\/","title":{"rendered":"Linked List Deleting Node"},"content":{"rendered":"

\"\"<\/p>\n

Introduction<\/h3>\n

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.<\/p>\n

Problem Statement<\/h3>\n

In this question, we are given a singly linked list and a value X<\/strong>. We have to delete the first occurrence of a node with the data X<\/strong> from the linked list.<\/p>\n

Note:<\/strong> Although there can be multiples nodes with value X<\/strong> in the linked list, but we have to only delete the first node with value X<\/strong> from the linked list.<\/p>\n

Problem Statement Understanding<\/h3>\n

Let\u2019s try to understand the problem statement with the help of examples.<\/p>\n

Suppose the given linked list is: 1 \u2192 1 \u2192 0 \u2192 2 \u2192 2 and the value to be deleted is 0.<\/p>\n

    \n
  • Now, according to the problem statement, we have to delete the first occurrence of the node containing the value 0.<\/li>\n
  • So, the linked list after deleting 0 will be 1 \u2192 1 \u2192 2 \u2192 2.<\/li>\n<\/ul>\n

    Suppose the list is:.<\/p>\n

    \"\"<\/p>\n

    and the value to be deleted is 2<\/p>\n

      \n
    • Now, in this case, we can see that there are two nodes with data 2 in the linked list. According to the problem statement, we only need to delete the first occurrence of the node with value 2 from the linked list.<\/li>\n
    • Our output linked list after deletion will be <\/li>\n<\/ul>\n

      \"\"<\/p>\n

      Some more examples<\/h5>\n

      Sample Input 1: 1 \u2192 2 \u2192 3 \u21924, Value to be deleted (X) = 2
      \nSample Output 1: 1 \u2192 3 \u2192 4<\/p>\n

      Sample Input 2: 1 \u2192 1 \u2192 2 \u21922, Value to be deleted (X) = 1
      \nSample Output 2: 1 \u2192 2 \u2192 2<\/p>\n

      Now, I think from the above examples, the problem statement is clear. Let\u2019s see how we can approach it.<\/p>\n

      Before moving to the approach section, try to think about how can you approach this problem.<\/p>\n

        \n
      • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.<\/li>\n<\/ul>\n

        Let\u2019s move to the approach section.<\/p>\n

        Approach (Iterative)<\/h3>\n

        Let us first think about what we should do to delete a node from a linked list. <\/p>\n

        Let us take an example. 1 \u2192 2 \u2192 3 \u2192 4. Now, to delete 2 from the list, what should we do? <\/p>\n

          \n
        • What if we make 1 point to 3 instead of 2 ? Yes. That\u2019s the essence.<\/li>\n<\/ul>\n

          To delete a node P<\/strong> from a linked list, we have to traverse to its previous node and make it point to the P<\/strong>‘s next node.<\/p>\n

          Let\u2019s see the algorithm.<\/p>\n

          Algorithm<\/h3>\n
            \n
          • Create a pointer temp<\/strong> and make it point to the head of the list and also create a pointer prev<\/strong> and point it to NULL.<\/li>\n
          • If the head contains the value X<\/strong>, make head = temp \u2192 next<\/strong>, and then delete temp<\/strong>. <\/li>\n
          • Else, we will traverse the list with temp<\/strong> and store temp<\/strong> in pointer prev<\/strong> before incrementing it.\n
              \n
            • The loop will run till temp \u2192 data! = X<\/strong>. <\/li>\n
            • As soon as temp \u2192 data = X<\/strong>, the loop will break. <\/li>\n<\/ul>\n<\/li>\n
            • As we were storing temp<\/strong> in prev<\/strong> before incrementing it, so prev<\/strong> now points to the previous node of the node which we want to delete. <\/li>\n
            • Now, we will simply do prev -> next = temp -> next<\/strong>, as discussed in the approach. <\/li>\n
            • Finally, delete temp<\/strong>. <\/li>\n
            • In this way, the first occurrence of a node with value X will be deleted. If the list is traversed and the value is not found, we will simply return.<\/li>\n<\/ul>\n

              Dry Run<\/h3>\n

              \"\"<\/p>\n

              Code Implementation<\/h3>\n\t\t\t\t\t\t