{"id":4840,"date":"2023-09-06T18:08:06","date_gmt":"2023-09-06T12:38:06","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4840"},"modified":"2023-09-06T18:08:08","modified_gmt":"2023-09-06T12:38:08","slug":"delete-node-in-a-linked-list","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/delete-node-in-a-linked-list\/","title":{"rendered":"Delete Node in a Linked List"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach-iterative\">Approach: Iterative<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#practice-question-\">Practice Question: <\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-how-to-delete-a-node-from-the-end-of-the-linked-list\">Q.1: How to delete a node from the end of the linked list?<\/a><\/li><li><a href=\"#q2-what-is-the-time-complexity-and-space-complexity-of-the-iterative-approach\">Q.2: What is the time complexity and space complexity of the iterative approach?<\/a><\/li><\/ul><li><a href=\"#additional-resources\">Additional Resources<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given the linked list. The task is to delete the node of the linked list and return the list.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong> 4 -&gt; 5 -&gt; 1 -&gt; 9<br><strong>Key =<\/strong> 5<br><strong>Output:<\/strong> 4 -&gt; 1 -&gt; 9 -&gt; NULL<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"640\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-5019 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example-1024x640.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example-1024x640.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example-300x188.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example-768x480.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example-380x238.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example-550x344.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example-800x500.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example-1160x725.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Example.png 1200w\" ><\/figure>\n\n\n\n<p><strong>Input:<\/strong> 10 -&gt; 20 -&gt; 30 -&gt; NULL<br><strong>Key =<\/strong> 20<br><strong>Output:<\/strong> 10 -&gt; 30 -&gt; NULL<\/p>\n\n\n\n<h2 id=\"approach-iterative\">Approach: Iterative<\/h2>\n\n\n\n<p>The approach is based on a few observations.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>If the node to be deleted is the head node, then simply point the head to the second node of the linked list.<\/li><li>For all other nodes:<ul><li>Traverse the linked list and for the current node <strong>curr, <\/strong>check whether the next node contains the key that needs to be deleted.<ul><li>If true, point <strong>curr -&gt; next <\/strong>to <strong>curr -&gt; next -&gt; next<\/strong>.<\/li><li>Else, keep traversing the list until the end of the linked list.<\/li><\/ul><\/li><\/ul><\/li><\/ul>\n\n\n\n<p>The following illustration will make the approach more clear.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"726\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-5020 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-1024x726.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-1024x726.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-300x213.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-768x545.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-1536x1089.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-380x269.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-550x390.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-800x567.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration-1160x823.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Illustration.png 1630w\" ><\/figure>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void deleteNode(struct node ** head, int key) {\n  struct node * temp;\n  if (( * head) -> data == key) {\n    temp = * head;\n    * head = ( * head) -> next;\n    free(temp);\n  } else {\n    struct node * current = * head;\n    while (current -> next != NULL) {\n      if (current -> next -> data == key) {\n        temp = current -> next;\n        current -> next = current -> next -> next;\n        free(temp);\n        break;\n      } else\n        current = current -> next;\n    }\n  }\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> void deleteNode(int key) {\n  Node temp = head, prev = null;\n  if (temp != null &amp;&amp; temp.data == key) {\n    head = temp.next;\n    return;\n  }\n  while (temp != null &amp;&amp; temp.data != key) {\n    prev = temp;\n    temp = temp.next;\n  }\n  if (temp == null)\n    return;\n \n  prev.next = temp.next;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def deleteNode(key):\n    temp = head\n    if temp is not None:\n        if temp.data == key:\n            self.head = temp.next\n            temp = None\n            return\n \n    while temp is not None:\n        if temp.data == key:\n            break\n        prev = temp\n        temp = temp.next\n \n    if temp == None:\n        return\n \n    prev.next = temp.next\n \n    temp = None<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N), where N is the total nodes of the linked list.<\/li><li><strong>Space Complexity:<\/strong> O(1) since no extra space is used.<\/li><\/ul>\n\n\n\n<h2 id=\"practice-question-\"><span id=\"practice-question\">Practice Question: <\/span><\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/remove-nth-node-from-list-end\/\" target=\"_blank\">Remove Nth Node from List End<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-how-to-delete-a-node-from-the-end-of-the-linked-list\"><span id=\"q-1-how-to-delete-a-node-from-the-end-of-the-linked-list\">Q.1: How to delete a node from the end of the linked list?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> If the node to be deleted is at the end of the linked list, traverse till the second last node, say <strong>curr<\/strong>, and mark <strong>curr -> next = NULL<\/strong> and free the memory.<\/p>\n\n\n\n<h3 id=\"q2-what-is-the-time-complexity-and-space-complexity-of-the-iterative-approach\"><span id=\"q-2-what-is-the-time-complexity-and-space-complexity-of-the-iterative-approach\">Q.2: What is the time complexity and space complexity of the iterative approach?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> The time complexity is O(N) and the space complexity is O(1), where N is the total node of the linked list.<\/p>\n\n\n\n<h2 id=\"additional-resources\">Additional Resources<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/detect-loop-in-linked-list\/\" target=\"_blank\">Detect Loop in Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/reverse-a-linked-list\/\" target=\"_blank\">Reverse a Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/add-two-numbers-represented-by-linked-lists\/\" target=\"_blank\">Add Two Numbers Represented by Linked Lists<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/intersection-of-two-linked-lists\/\" target=\"_blank\">Intersection of Two Linked Lists<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/linked-list-interview-questions\/\" target=\"_blank\">Linked List Interview Questions<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/linked-list-mcq\/\" target=\"_blank\">Linked List MCQ<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/application-of-linked-list\/\" target=\"_blank\">Application of Linked List<\/a><\/li><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/blog\/types-of-linked-list\/\" target=\"_blank\">Types of Linked List<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given the linked list. The task is to delete the node of the linked list and&hellip;\n","protected":false},"author":5,"featured_media":5018,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[673],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4840"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=4840"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4840\/revisions"}],"predecessor-version":[{"id":23632,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4840\/revisions\/23632"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5018"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4840"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4840"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4840"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}