{"id":710,"date":"2020-06-23T23:27:27","date_gmt":"2020-06-23T15:27:27","guid":{"rendered":"http:\/\/www.guanhaobo.cn\/?p=710"},"modified":"2020-06-23T23:27:27","modified_gmt":"2020-06-23T15:27:27","slug":"jz14-%e9%93%be%e8%a1%a8%e4%b8%ad%e5%80%92%e6%95%b0%e7%ac%ack%e4%b8%aa%e7%bb%93%e7%82%b9","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=710","title":{"rendered":"JZ14 \u2014 \u94fe\u8868\u4e2d\u5012\u6570\u7b2ck\u4e2a\u7ed3\u70b9"},"content":{"rendered":"<h3>\u9898\u76ee\u63cf\u8ff0<\/h3>\n<p>\u8f93\u5165\u4e00\u4e2a\u94fe\u8868\uff0c\u8f93\u51fa\u8be5\u94fe\u8868\u4e2d\u5012\u6570\u7b2ck\u4e2a\u7ed3\u70b9\u3002<\/p>\n<h3>\u89e3\u6cd5\u4e00<\/h3>\n<p>\u627e\u4e2a\u5bb9\u5668\u5c06\u94fe\u8868\u4fdd\u5b58\u4e0b\u6765\uff0c\u7136\u540e\u8f93\u51fa\u5012\u6570\u7b2ck\u4e2a\u5143\u7d20\u3002<br \/>\n\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a<code>O(n)<\/code>\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3a<code>O(n)<\/code><br \/>\n\u8fd9\u79cd\u89e3\u6cd5\u7531\u4e8e\u9700\u8981\u989d\u5916\u5f00\u5bb9\u5668\uff0c\u5360\u7528\u5185\u5b58\u7a7a\u95f4\uff0c\u6240\u4ee5\u5e76\u4e0d\u662f\u4e00\u4e2a\u4f18\u96c5\u7684\u89e3\u6cd5\u3002<\/p>\n<h5>C++<\/h5>\n<pre><code class=\"language-cpp line-numbers\">\/*\nstruct ListNode {\n    int val;\n    struct ListNode *next;\n    ListNode(int x) :\n            val(x), next(NULL) {\n    }\n};*\/\nclass Solution\n{\npublic:\n    ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)\n    {\n        vector&lt;ListNode *&gt; v;\n        while (pListHead != NULL)\n        {\n            v.push_back(pListHead);\n            pListHead = pListHead-&gt;next;\n        }\n        if (k &gt; v.size())\n            return NULL;\n        return v[v.size() - k];\n    }\n};\n<\/code><\/pre>\n<h5>Java<\/h5>\n<pre><code class=\"language-java line-numbers\">\/*\npublic class ListNode {\n    int val;\n    ListNode next = null;\n\n    ListNode(int val) {\n        this.val = val;\n    }\n}*\/\nimport java.util.*;\n\npublic class Solution {\n    public ListNode FindKthToTail(ListNode head, int k) {\n        ArrayList&lt;ListNode&gt; list = new ArrayList&lt;&gt;();\n        while (head != null) {\n            list.add(head);\n            head = head.next;\n        }\n        if (k &gt; list.size() || k &lt;= 0)\n            return null;\n        return list.get(list.size() - k);\n    }\n}\n<\/code><\/pre>\n<h3>\u89e3\u6cd5\u4e8c<\/h3>\n<p>\u904d\u5386\u4e00\u904d\uff0c\u8bb0\u5f55\u7ed3\u70b9\u7684\u603b\u6570<code>size<\/code>\uff0c\u7136\u540e\u518d\u904d\u5386\u4e00\u904d\uff0c\u8f93\u51fa\u6b63\u5411\u7b2c<code>size-k+1<\/code>\u4e2a\u7ed3\u70b9\u3002<br \/>\n\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a<code>O(n)<\/code>\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3a<code>O(1)<\/code><\/p>\n<h5>C++<\/h5>\n<pre><code class=\"language-cpp line-numbers\">\/*\nstruct ListNode {\n    int val;\n    struct ListNode *next;\n    ListNode(int x) :\n            val(x), next(NULL) {\n    }\n};*\/\nclass Solution\n{\npublic:\n    ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)\n    {\n        int size = 0, index = 0;\n        for (ListNode *p = pListHead; p != NULL; p = p-&gt;next)\n            size++;\n        if (k &gt; size)\n            return NULL;\n        for (ListNode *p = pListHead; p != NULL; p = p-&gt;next)\n        {\n            if (++index == size - k + 1)\n                return p;\n        }\n    }\n};\n<\/code><\/pre>\n<h5>Java<\/h5>\n<pre><code class=\"language-java line-numbers\">\/*\npublic class ListNode {\n    int val;\n    ListNode next = null;\n\n    ListNode(int val) {\n        this.val = val;\n    }\n}*\/\npublic class Solution {\n    public ListNode FindKthToTail(ListNode head, int k) {\n        int size = 0, index = 0;\n        for (ListNode p = head; p != null; p = p.next)\n            size++;\n        if (k &gt; size || k &lt;= 0)\n            return null;\n        for (ListNode p = head; p != null; p = p.next)\n            if (++index == size - k + 1)\n                return p;\n        return null;\n    }\n}\n<\/code><\/pre>\n<h3>\u89e3\u6cd5\u4e09<\/h3>\n<p>\u4f7f\u7528\u4e24\u4e2a\u6307\u9488<code>left<\/code>\u548c<code>right<\/code>\u4ece\u5de6\u5230\u53f3\u904d\u5386\uff0c\u4e24\u6307\u9488\u4e2d\u95f4\u76f8\u5dee<code>k<\/code>\u4e2a\u7ed3\u70b9\uff0c\u5f53<code>right<\/code>\u5230\u8fbe\u672b\u5c3e\u6307\u5411<code>NULL<\/code>\u7684\u65f6\u5019\uff0c<code>left<\/code>\u5bf9\u5e94\u7684\u5c31\u662f\u5012\u6570\u7b2ck\u4e2a\u7ed3\u70b9\u3002<br \/>\n\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a<code>O(n)<\/code>\uff0c\u7a7a\u95f4\u590d\u6742\u5ea6\u4e3a<code>O(1)<\/code><\/p>\n<h5>C++<\/h5>\n<pre><code class=\"language-cpp line-numbers\">class Solution\n{\npublic:\n    ListNode *FindKthToTail(ListNode *pListHead, unsigned int k)\n    {\n        ListNode *left = pListHead, *right = pListHead;\n        int count = 0;\n        while (right)\n        {\n            count++;\n            right = right-&gt;next;\n            if (count &gt; k)\n                left = left-&gt;next;\n        }\n        if (count &lt; k)\n            return NULL;\n        return left;\n    }\n};\n<\/code><\/pre>\n<h5>Java<\/h5>\n<pre><code class=\"language-java line-numbers\">\/*\npublic class ListNode {\n    int val;\n    ListNode next = null;\n\n    ListNode(int val) {\n        this.val = val;\n    }\n}*\/\npublic class Solution {\n    public ListNode FindKthToTail(ListNode head, int k) {\n        int count = 0;\n        ListNode left = head, right = head;\n        while (right != null) {\n            right = right.next;\n            if (++count &gt; k)\n                left = left.next;\n        }\n        if (count &lt; k || k &lt;= 0)\n            return null;\n        return left;\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u63cf\u8ff0 \u8f93\u5165\u4e00\u4e2a\u94fe\u8868\uff0c\u8f93\u51fa\u8be5\u94fe\u8868\u4e2d\u5012\u6570\u7b2ck\u4e2a\u7ed3\u70b9\u3002 \u89e3\u6cd5\u4e00 \u627e\u4e2a\u5bb9\u5668\u5c06\u94fe\u8868\u4fdd\u5b58\u4e0b\u6765\uff0c\u7136\u540e\u8f93\u51fa\u5012\u6570\u7b2ck\u4e2a\u5143\u7d20\u3002 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[39],"class_list":["post-710","post","type-post","status-publish","format-standard","hentry","category-algo","tag-offer"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/710","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=710"}],"version-history":[{"count":0,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/710\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=710"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=710"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=710"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}