Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1\u21922\u21923\u21924\u21925\u21926, if K = 3, then you must output 3\u21922\u21921\u21926\u21925\u21924; if K = 4, you must output 4\u21923\u21922\u21921\u21925\u21926. Sample Output:<\/b><\/p>\n <\/p>\n \u521d\u770b\u662f\u4e00\u9053\u5f88\u7b80\u5355\u7684\u9898\u76ee\uff0c\u5bf9\u94fe\u8868\u8fdb\u884c\u6709\u89c4\u5f8b\u7684\u53cd\u8f6c\u3002\u6211\u91c7\u53d6\u7684\u65b9\u6848\u5982\u4e0b\uff1a \u8fd9\u65f6\u5019\u7684\u6b63\u786e\u8f93\u51fa\u662f\uff1a<\/p>\n <\/p>\n <\/p>\n <\/p>\n \uff08\u8fd9\u4e2a\u7ed3\u679c\u8fd8\u6709\u4f18\u5316\u7684\u7a7a\u95f4\uff0c\u4e0d\u8fc7\u65e2\u7136\u5df2\u7ecf<400ms\u4e86\u6211\u5c31\u4e0d\u7ba1\u5566~\uff09<\/p>\n \u539f\u9898\uff1a Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1\u21922\u21923\u21924\u21925\u21926, if K = 3, then you must output 3\u21922\u21921\u21926\u21925\u21924; if K = 4, you must output 4\u21923\u21922\u21921\u21925\u21926. Input Specification: Each input file contains one test […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[84],"class_list":["post-1464","post","type-post","status-publish","format-standard","hentry","category-study","tag-pat"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1464","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1464"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1464\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1464"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1464"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1464"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nInput Specification:<\/b>
\nEach input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105<\/sup>) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
\nThen N lines follow, each describes a node in the format:
\nAddress Data Next<\/i>
\nwhere Address<\/i> is the position of the node, Data<\/i> is an integer, and Next<\/i> is the position of the next node.
\nOutput Specification:<\/b>
\nFor each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
\nSample Input:<\/b><\/p>\n00100 6 4\n00000 4 99999\n00100 1 12309\n68237 6 -1\n33218 3 00000\n99999 5 68237\n12309 2 33218\n<\/pre>\n
00000 4 33218\n33218 3 12309\n12309 2 00100\n00100 1 99999\n99999 5 68237\n68237 6 -1<\/pre>\n
\n\u5206\u6790\uff1a<\/strong><\/span><\/h1>\n
\n1.\u8bfb\u53d6\u8f93\u5165\uff0c\u7136\u540e\u94fe\u8868\u6309\u5176\u5730\u5740\u5b58\u653e\u5230map\u4e2d\uff08\u5f53\u7136\u6709\u7325\u7410\u7684\u4eba\u53ef\u4ee5\u5b58\u653e\u5230\u6570\u7ec4\u91cc\u7528\u7a7a\u95f4\u6362\u65f6\u95f4\uff09\uff1b
\n2.\u6309\u7167\u94fe\u8868\u7684\u5934\u6307\u9488\u987a\u7740\u4e0b\u53bb\u8bfb\u53d6\u94fe\u8868\u3002\u5efa\u4e00\u4e2a\u6808\uff0c\u5f53\u6ca1\u6709\u8fbe\u5230K\u4e2a\u65f6\uff0c\u6bcf\u4e2a\u8bfb\u53d6\u5230\u7684\u503c\u538b\u5165\u6808\u91cc\uff0c\u7136\u540e\u96c6\u9f50K\u4e2a\u7684\u65f6\u5019\u8f93\u51fa\u3002\u6280\u5de7\u662f\u4e00\u884c\u8f93\u51fa\u7684\u4e1c\u897f\u53ef\u4ee5\u5206\u62c6\u5206\u6210\u4e24\u5757\uff0c\u5373\u9664\u7b2c\u4e00\u884c\u4e0e\u6700\u540e\u4e00\u884c\u7279\u6b8a\u5916\uff0c\u5176\u4ed6\u6bcf\u4e24\u884c\u90fd\u662f:
\n[\u4e0a\u4e00\u5730\u5740 ] [\u4e0a\u4e2a\u503c ] [\u5f53\u524d\u5730\u5740<\/strong>]
\n[\u5f53\u524d\u5730\u5740<\/strong>] [\u5f53\u524d\u503c<\/strong>] [\u4e0b\u4e00\u5730\u5740]
\n\u4e5f\u5c31\u662f\u8bf4\u5f97\u5230\u5f53\u524d\u8282\u70b9\u540e\uff0c\u53ea\u9700\u8981\u8865\u9f50\u4e0a\u4e00\u884c\u7684”\u5f53\u524d\u5730\u5740”\u548c\u5f53\u524d\u884c\u524d\u4e24\u9879\u5373\u53ef\uff0c\u7b49\u5230\u4e0b\u4e00\u4e2a\u8282\u70b9\u8bfb\u5165\u65f6\u518d\u8865\u4e0a\u8fd9\u4e00\u884c\u7684\u6700\u540e\u4e00\u4e2a\u201c\u4e0b\u4e00\u5730\u5740\u201d\u3002
\n3.\u6700\u540e\uff0c\u672b\u5c3e\u522b\u5fd8\u4e86NULL\u6307\u9488\u201c-1\u201d
\n\u4e0a\u9762\u7684\u7b97\u6cd5\u590d\u6742\u5ea6\u662fO(N)
\n
\n\u4f46\u662f\u8bf7\u52a1\u5fc5\u8003\u8651\u4e0b\u9762\u51e0\u4e2a\u7279\u6b8a\u60c5\u51b5\uff1a<\/strong>
\n1. K=1, K=N
\n2. \u7ed9\u7684\u5934\u6307\u9488\u4e0d\u662f\u6574\u6761\u94fe\u7684\u5934\u6307\u9488\uff0c\u800c\u662f\u4e2d\u95f4\u67d0\u4e2a\u8282\u70b9\u7684\u3002<\/span><\/strong>\u8fd9\u4e2a\u95ee\u9898\u662f\u6700\u540e\u4e00\u4e2a\u6d4b\u8bd5\u70b9\u6d4b\u8bd5\u7684\u4e1c\u897f\u3002\u6211\u4e00\u5f00\u59cb\u4e5f\u8bd5\u4e86\u597d\u591a\u65e0\u679c\uff0c\u8fd8\u597d\u641c\u5230\u4e86\u8fd9\u7bc7\u6587\u7ae0\u672b\u5c3e\u7684\u8bc4\u8bba\u90e8\u5206<\/a>\u624d\u5f97\u5230\u542f\u53d1\uff01\u53e6\u5916\u6d4b\u8bd5\u70b96\u4e0d\u4f1a\u8003\u8651\u7ed9\u7684\u6d4b\u8bd5\u4f8b\u6709\u591a\u4e2anext\u6307\u9488\u5f0fNULL\u6307\u9488\uff08-1\uff09\u7684\u60c5\u51b5\uff0c\u6709\u4e9b\u535a\u5ba2\u4e2d\u8fd9\u79cd\u8bf4\u6cd5\u662f\u9519\u8bef\u7684\u3002<\/strong>
\n\u4f8b\u5982\uff1a<\/p>\n00000 6 4\n00000 4 99999\n00100 1 12309\n68237 6 -1\n33218 3 00000\n99999 5 68237\n12309 2 33218<\/pre>\n
00000 4 99999\n99999 5 68237\n68237 6 -1<\/pre>\n
\n\u4ee3\u7801<\/h1>\n
#include <iostream>\n#include <map>\n#include <stack>\n#include <string.h>\nusing namespace std;\nstruct Node\n{\n\tchar fake_addr[6];\n\tchar fake_next[6];\n\tint data;\n};\nint main()\n{\n\tchar pStart[6];\n\tint N, K;\n\tcin >> pStart >> N >> K;\n\tmap<int, Node> mapNodes;\n\tint multiEnd = 0;\n\tfor (int i = 0; i < N; i++)\n\t{\n\t\t\/\/Read from input\n\t\tchar addr[6], next[6];\n\t\tint data;\n\t\tcin >> addr >> data >> next;\n\t\tif (strcmp(next, \"-1\") == 0)\n\t\t\tmultiEnd++;\n\t\tNode node;\n\t\tnode.data = data;\n\t\tstrcpy(node.fake_addr, addr);\n\t\tstrcpy(node.fake_next, next);\n\t\tint key = atoi(addr);\n\t\tmapNodes[key] = node;\n\t}\n\tif (true)\n\t{\n\t\t\/\/\u5947\u602a\u7684\u7684\u60c5\u51b5\uff0c\u9700\u8981\u626b\u94fe\u4e86\n\t\tint count = 0;\n\t\tint nextPtr = atoi(pStart);\n\t\twhile (nextPtr != -1)\n\t\t{\n\t\t\tnextPtr = atoi(mapNodes[nextPtr].fake_next);\n\t\t\tcount++;\n\t\t}\n\t\tN = count;\n\t}\n\tstack<Node> workingStack;\n\tconst int LIMIT = N - N % K;\n\tint currentFakePtr = atoi(pStart);\n\tbool firstLine = true;\n\t\/\/\u80fd\u6574\u9664\u7684\u8303\u56f4\n\tfor (int i = 0; i < LIMIT; i++)\n\t{\n\t\tif (true)\n\t\t{\n\t\t\t\/\/\u5c06node\u538b\u5165\u6808\u51c6\u5907\u8f93\u51fa\n\t\t\tif (currentFakePtr == -1)\n\t\t\t{\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tNode currentNode = mapNodes[currentFakePtr];\n\t\t\tworkingStack.push(currentNode);\n\t\t\tcurrentFakePtr = atoi(currentNode.fake_next);\n\t\t}\n\t\tif (i%K == K-1)\n\t\t{\n\t\t\t\/\/\u9010\u6761\u5f39\u6808\u5e76\u8f93\u51fa (\u9664\u6700\u540e\u4e00\u4e2a\u8282\u70b9\u7684next\u5730\u5740)\n\t\t\twhile (!workingStack.empty())\n\t\t\t{\n\t\t\t\tNode currentNode = workingStack.top();\n\t\t\t\tif (!firstLine)\n\t\t\t\t\tcout << currentNode.fake_addr << endl; \/\/\u4e0a\u4e00\u884c\u7684\u672b\u5c3e\n\t\t\t\tcout << currentNode.fake_addr << \" \" << currentNode.data << \" \"; \/\/\u672c\u884c\u7684\u524d\u4e24\u4e2a\u5143\u7d20\n\t\t\t\tworkingStack.pop();\n\t\t\t\tfirstLine = false;\n\t\t\t}\n\t\t}\n\t}\n\t\/\/\u4e0d\u80fd\u6574\u9664\u7684\u8303\u56f4\uff0c\u6309\u987a\u5e8f\u8f93\u51fa\n\t\/\/\u9700\u8981\u8003\u8651\u4e00\u5f00\u59cb\u5c31\u4e0d\u80fd\u6574\u9664\u7684\u60c5\u51b5 (LIMIT = 0)\n\tfor (int i = LIMIT; i < N; i++)\n\t{\n\t\tif (currentFakePtr == -1)\n\t\t{\n\t\t\tbreak;\n\t\t}\n\t\tNode currentNode = mapNodes[currentFakePtr];\n\t\tif (!firstLine)\n\t\t\tcout << currentNode.fake_addr << endl; \/\/\u4e0a\u4e00\u884c\u7684\u672b\u5c3e\n\t\tcout << currentNode.fake_addr << \" \" << currentNode.data << \" \"; \/\/\u672c\u884c\u7684\u524d\u4e24\u4e2a\u5143\u7d20\n\t\tcurrentFakePtr = atoi(currentNode.fake_next);\n\t\tfirstLine = false;\n\t}\n\tcout << \"-1\";\n\treturn 0;\n}<\/pre>\n
\n\u6d4b\u8bd5\u70b9<\/h2>\n
\n\n
\n \n\u6d4b\u8bd5\u70b9<\/th>\n \u7ed3\u679c<\/th>\n \u7528\u65f6(ms)<\/th>\n \u5185\u5b58(kB)<\/th>\n \u5f97\u5206\/\u6ee1\u5206<\/th>\n<\/tr>\n<\/thead>\n \n 0<\/td>\n \u7b54\u6848\u6b63\u786e<\/span><\/td>\n 1<\/td>\n 360<\/td>\n 12\/12<\/td>\n<\/tr>\n \n 1<\/td>\n \u7b54\u6848\u6b63\u786e<\/span><\/td>\n 1<\/td>\n 232<\/td>\n 3\/3<\/td>\n<\/tr>\n \n 2<\/td>\n \u7b54\u6848\u6b63\u786e<\/span><\/td>\n 1<\/td>\n 360<\/td>\n 2\/2<\/td>\n<\/tr>\n \n 3<\/td>\n \u7b54\u6848\u6b63\u786e<\/span><\/td>\n 1<\/td>\n 232<\/td>\n 2\/2<\/td>\n<\/tr>\n \n 4<\/td>\n \u7b54\u6848\u6b63\u786e<\/span><\/td>\n 1<\/td>\n 232<\/td>\n 2\/2<\/td>\n<\/tr>\n \n 5<\/td>\n \u7b54\u6848\u6b63\u786e<\/span><\/td>\n 326<\/td>\n 8424<\/td>\n 3\/3<\/td>\n<\/tr>\n \n 6<\/td>\n \u7b54\u6848\u6b63\u786e<\/span><\/td>\n 1<\/td>\n 360<\/td>\n 1\/1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n","protected":false},"excerpt":{"rendered":"