{"id":96,"date":"2023-04-12T23:50:59","date_gmt":"2023-04-12T15:50:59","guid":{"rendered":"https:\/\/blog.49cc.top\/?p=96"},"modified":"2023-04-12T23:50:59","modified_gmt":"2023-04-12T15:50:59","slug":"%e5%8f%98%e5%bd%a2%e7%9a%84%e9%93%be%e8%a1%a8%e5%8f%8d%e8%bd%ac","status":"publish","type":"post","link":"https:\/\/blog.rrr.ink\/?p=96","title":{"rendered":"\u53d8\u5f62\u7684\u94fe\u8868\u53cd\u8f6c"},"content":{"rendered":"\n

\u9898\u76ee\u63cf\u8ff0\uff1a<\/strong><\/p>\n\n\n\n

\u7ed9\u5b9a\u4e00\u4e2a\u5355\u94fe\u8868\u7684\u5934\u8282\u70b9 head,\u5b9e\u73b0\u4e00\u4e2a\u8c03\u6574\u5355\u94fe\u8868\u7684\u51fd\u6570\uff0c\u4f7f\u5f97\u6bcfK\u4e2a\u8282\u70b9\u4e4b\u95f4\u4e3a\u4e00\u7ec4\u8fdb\u884c\u9006\u5e8f\uff0c\u5e76\u4e14\u4ece\u94fe\u8868\u7684\u5c3e\u90e8\u5f00\u59cb\u7ec4\u8d77\uff0c\u5934\u90e8\u5269\u4f59\u8282\u70b9\u6570\u91cf\u4e0d\u591f\u4e00\u7ec4\u7684\u4e0d\u9700\u8981\u9006\u5e8f\u3002\uff08\u4e0d\u80fd\u4f7f\u7528\u961f\u5217\u6216\u8005\u6808\u4f5c\u4e3a\u8f85\u52a9\uff09<\/p>\n\n\n\n

\u793a\u4f8b\uff1a<\/strong><\/p>\n\n\n\n

\u94fe\u8868:1->2->3->4->5->6->7->8->null, K = 3<\/code>\u3002\u90a3\u4e48 6->7->8<\/code>\uff0c3->4->5<\/code>\uff0c1->2<\/code>\u5404\u4f4d\u4e00\u7ec4\u3002\u8c03\u6574\u540e\uff1a1->2->5->4->3->8->7->6->null<\/code>\u3002\u5176\u4e2d 1\uff0c2\u4e0d\u8c03\u6574\uff0c\u56e0\u4e3a\u4e0d\u591f\u4e00\u7ec4\u3002<\/p>\n\n\n\n

\u601d\u8def\uff1a<\/strong><\/p>\n\n\n\n

\u6839\u636e\u94fe\u8868\u957f\u5ea6 length<\/code> \u548c\u7ed9\u5b9a\u7684\u6574\u6570 k<\/code>\uff0c\u8ba1\u7b97\u9700\u8981\u53cd\u8f6c\u7684\u7ec4\u6570 groups<\/code>\uff0c\u4ee5\u53ca\u4e0d\u8fdb\u884c\u53cd\u8f6c\u7684\u5934\u90e8\u5269\u4f59\u8282\u70b9\u6570\u91cf remaining<\/code>\u3002<\/p>\n\n\n\n

\u521b\u5efa\u4e00\u4e2a\u54d1\u8282\u70b9 dummy<\/code>\uff0c\u4f7f\u5176\u6307\u5411\u94fe\u8868\u7684\u5934\u8282\u70b9\u3002\u63a5\u4e0b\u6765\uff0c\u521b\u5efa\u4e00\u4e2a\u6307\u9488 preGroupEnd<\/code>\uff0c\u521d\u59cb\u5316\u4e3a\u6307\u5411\u54d1\u8282\u70b9\u3002\u5c06 preGroupEnd<\/code> \u6307\u9488\u5411\u540e\u79fb\u52a8 remaining<\/code> \u4e2a\u8282\u70b9\uff0c\u4f7f\u5176\u6307\u5411\u6700\u540e\u4e00\u4e2a\u4e0d\u8fdb\u884c\u53cd\u8f6c\u7684\u5934\u90e8\u5269\u4f59\u8282\u70b9\u3002\u8fd9\u6837\uff0cpreGroupEnd<\/code> \u521d\u59cb\u65f6\u6307\u5411\u4e0d\u9700\u8981\u53cd\u8f6c\u7684\u90e8\u5206\u7684\u672b\u5c3e\u3002<\/p>\n\n\n\n

<\/p>\n\n\n\n

\u5b9e\u73b0\uff1a<\/strong><\/p>\n\n\n\n

package main\n\nimport (\n\t\"fmt\"\n)\n\ntype ListNode struct {\n\tVal  int\n\tNext *ListNode\n}\n\nfunc reverseKGroupFromEnd(head *ListNode, k int) *ListNode {\n\tif head == nil || k <= 1 {\n\t\treturn head\n\t}\n\n\t\/\/ \u8ba1\u7b97\u94fe\u8868\u957f\u5ea6\n\tlength := 0\n\tcur := head\n\tfor cur != nil {\n\t\tlength++\n\t\tcur = cur.Next\n\t}\n\n\t\/\/ \u8ba1\u7b97\u9700\u8981\u53cd\u8f6c\u7684\u7ec4\u6570\n\tgroups := length \/ k\n\n\tif groups == 0 {\n\t\treturn head\n\t}\n\n\t\/\/ \u8ba1\u7b97\u5269\u4f59\u8282\u70b9\u6570\u91cf\n\tremaining := length % k\n\n\tdummy := &ListNode{Next: head}\n\tpreGroupEnd := dummy\n\tfor i := 0; i < remaining; i++ {\n\t\tpreGroupEnd = preGroupEnd.Next\n\t}\n\n\tfor i := 0; i < groups; i++ {\n\t\tstart := preGroupEnd.Next\n\t\tend := preGroupEnd\n\t\tfor j := 0; j < k; j++ {\n\t\t\tend = end.Next\n\t\t}\n\t\tnextGroupStart := end.Next\n\t\tend.Next = nil\n\n\t\t\/\/ \u9006\u5e8f\u5f53\u524d\u7ec4\n\t\tnewStart, newEnd := reverseList(start)\n\t\tpreGroupEnd.Next = newStart\n\t\tnewEnd.Next = nextGroupStart\n\t\tpreGroupEnd = newEnd\n\t}\n\n\treturn dummy.Next\n}\n\nfunc reverseList(head *ListNode) (*ListNode, *ListNode) {\n\tvar prev *ListNode\n\tcur := head\n\n\tfor cur != nil {\n\t\tnext := cur.Next\n\t\tcur.Next = prev\n\t\tprev = cur\n\t\tcur = next\n\t}\n\n\treturn prev, head\n}\n\nfunc main() {\n\thead := &ListNode{1, &ListNode{2, &ListNode{3, &ListNode{4, &ListNode{5, &ListNode{6, &ListNode{7, &ListNode{8, nil}}}}}}}}\n\tk := 3\n\n\tnewHead := reverseKGroupFromEnd(head, k)\n\tfor newHead != nil {\n\t\tif newHead.Next == nil {\n\t\t\tfmt.Printf(\"%d -> null\", newHead.Val)\n\t\t} else {\n\t\t\tfmt.Printf(\"%d -> \", newHead.Val)\n\t\t}\n\t\tnewHead = newHead.Next\n\t}\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0\uff1a \u7ed9\u5b9a\u4e00\u4e2a\u5355\u94fe\u8868\u7684\u5934\u8282\u70b9 head,\u5b9e\u73b0\u4e00\u4e2a\u8c03\u6574\u5355\u94fe\u8868\u7684\u51fd\u6570\uff0c\u4f7f\u5f97\u6bcfK\u4e2a\u8282\u70b9\u4e4b\u95f4\u4e3a\u4e00\u7ec4\u8fdb\u884c\u9006\u5e8f\uff0c\u5e76\u4e14 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[7],"_links":{"self":[{"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/posts\/96"}],"collection":[{"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=96"}],"version-history":[{"count":2,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/posts\/96\/revisions"}],"predecessor-version":[{"id":98,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=\/wp\/v2\/posts\/96\/revisions\/98"}],"wp:attachment":[{"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=96"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=96"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.rrr.ink\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=96"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}