{"id":9020,"date":"2021-12-04T22:24:18","date_gmt":"2021-12-05T06:24:18","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9020"},"modified":"2021-12-04T22:24:48","modified_gmt":"2021-12-05T06:24:48","slug":"leetcode-2095-delete-the-middle-node-of-a-linked-list","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-2095-delete-the-middle-node-of-a-linked-list\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2095. Delete the Middle Node of a Linked List"},"content":{"rendered":"\n<p>You are given the&nbsp;<code>head<\/code>&nbsp;of a linked list.&nbsp;<strong>Delete<\/strong>&nbsp;the&nbsp;<strong>middle node<\/strong>, and return&nbsp;<em>the<\/em>&nbsp;<code>head<\/code>&nbsp;<em>of the modified linked list<\/em>.<\/p>\n\n\n\n<p>The&nbsp;<strong>middle node<\/strong>&nbsp;of a linked list of size&nbsp;<code>n<\/code>&nbsp;is the&nbsp;<code>\u230an \/ 2\u230b<sup>th<\/sup><\/code>&nbsp;node from the&nbsp;<strong>start<\/strong>&nbsp;using&nbsp;<strong>0-based indexing<\/strong>, where&nbsp;<code>\u230ax\u230b<\/code>&nbsp;denotes the largest integer less than or equal to&nbsp;<code>x<\/code>.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For&nbsp;<code>n<\/code>&nbsp;=&nbsp;<code>1<\/code>,&nbsp;<code>2<\/code>,&nbsp;<code>3<\/code>,&nbsp;<code>4<\/code>, and&nbsp;<code>5<\/code>, the middle nodes are&nbsp;<code>0<\/code>,&nbsp;<code>1<\/code>,&nbsp;<code>1<\/code>,&nbsp;<code>2<\/code>, and&nbsp;<code>2<\/code>, respectively.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/11\/16\/eg1drawio.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [1,3,4,7,1,2,6]\n<strong>Output:<\/strong> [1,3,4,1,2,6]\n<strong>Explanation:<\/strong>\nThe above figure represents the given linked list. The indices of the nodes are written below.\nSince n = 7, node 3 with value 7 is the middle node, which is marked in red.\nWe return the new list after removing this node. \n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/11\/16\/eg2drawio.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [1,2,3,4]\n<strong>Output:<\/strong> [1,2,4]\n<strong>Explanation:<\/strong>\nThe above figure represents the given linked list.\nFor n = 4, node 2 with value 3 is the middle node, which is marked in red.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/11\/16\/eg3drawio.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> head = [2,1]\n<strong>Output:<\/strong> [2]\n<strong>Explanation:<\/strong>\nThe above figure represents the given linked list.\nFor n = 2, node 1 with value 1 is the middle node, which is marked in red.\nNode 0 with value 2 is the only node remaining after removing node 1.<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The number of nodes in the list is in the range&nbsp;<code>[1, 10<sup>5<\/sup>]<\/code>.<\/li><li><code>1 &lt;= Node.val &lt;= 10<sup>5<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Fast \/ Slow pointers<\/strong><\/h2>\n\n\n\n<p>Use fast \/ slow pointers to find the previous node of the middle one, then skip the middle one.<\/p>\n\n\n\n<p>prev.next = prev.next.next<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  ListNode* deleteMiddle(ListNode* head) {\n    ListNode dummy(0, head);\n    ListNode* prev = &dummy;\n    ListNode* fast = head;\n    \/\/ prev points to the previous node of the middle one.\n    while (fast && fast->next) {\n      prev = prev->next;\n      fast = fast->next->next;\n    }    \n    prev->next = prev->next->next;\n    return dummy.next;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given the&nbsp;head&nbsp;of a linked list.&nbsp;Delete&nbsp;the&nbsp;middle node, and return&nbsp;the&nbsp;head&nbsp;of the modified linked list. The&nbsp;middle node&nbsp;of a linked list of size&nbsp;n&nbsp;is the&nbsp;\u230an \/ 2\u230bth&nbsp;node from&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[352,83,177,358],"class_list":["post-9020","post","type-post","status-publish","format-standard","hentry","category-list","tag-fast-slow","tag-list","tag-medium","tag-middle","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9020","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9020"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9020\/revisions"}],"predecessor-version":[{"id":9022,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9020\/revisions\/9022"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9020"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9020"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9020"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}