{"id":7397,"date":"2026-07-21T21:38:14","date_gmt":"2026-07-21T13:38:14","guid":{"rendered":"https:\/\/i007.cc\/wordpress\/?p=7397"},"modified":"2026-07-21T21:38:14","modified_gmt":"2026-07-21T13:38:14","slug":"%e5%8f%8d%e8%bd%ac%e9%93%be%e8%a1%a8%ef%bc%88reverse-linked-list%ef%bc%89","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/7397","title":{"rendered":"\u53cd\u8f6c\u94fe\u8868\uff08Reverse Linked List\uff09"},"content":{"rendered":"

\u529b\u6263\u7b2c 206 \u9898\u3002\u628a\u4e00\u6761\u5355\u94fe\u8868\u539f\u5730\u53cd\u8f6c\uff0c\u8fd4\u56de\u65b0\u5934\u8282\u70b9\u3002<\/p>\n

\n

\u89e3\u6cd5\u4e00\uff1a\u8fed\u4ee3\uff08\u6700\u4f18\uff0cO(1) \u7a7a\u95f4\uff09\u2b50<\/h4>\n

\u7528\u4e09\u4e2a\u6307\u9488\u6eda\u52a8\u63a8\u8fdb\uff0c\u6bcf\u6b21\u628a\u5f53\u524d\u8282\u70b9\u7684 next<\/code> \u6307\u9488\u6389\u5934\u3002<\/p>\n

\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
ListNode* reverseList(ListNode* head) {\r\n    ListNode* prev = nullptr;\r\n    ListNode* curr = head;\r\n\r\n    while (curr != nullptr) {\r\n        ListNode* next = curr->next;  \/\/ \u5148\u4fdd\u5b58\u540e\u7ee7\uff0c\u5426\u5219\u65ad\u94fe\u540e\u627e\u4e0d\u5230\r\n        curr->next = prev;            \/\/ \u6389\u5934\r\n        prev = curr;                  \/\/ prev \u524d\u8fdb\r\n        curr = next;                  \/\/ curr \u524d\u8fdb\r\n    }\r\n\r\n    return prev;  \/\/ curr \u4e3a null \u65f6\uff0cprev \u6b63\u597d\u662f\u65b0\u5934\r\n}<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u8d70\u4e00\u904d\u4f8b\u5b50\uff1a<\/strong><\/p>\n
\n
\n
<\/div>\n<\/div>\n
\n
\u539f\u94fe\u8868: 1 \u2192 2 \u2192 3 \u2192 4 \u2192 null\r\n\r\n\u521d\u59cb:   prev=null, curr=1\r\n\r\n\u7b2c1\u6b65:  next=2, 1\u2192null, prev=1, curr=2\r\n\u7b2c2\u6b65:  next=3, 2\u21921,    prev=2, curr=3\r\n\u7b2c3\u6b65:  next=4, 3\u21922,    prev=3, curr=4\r\n\u7b2c4\u6b65:  next=null, 4\u21923, prev=4, curr=null\r\n\r\n\u8fd4\u56de prev=4\uff0c\u5373\u65b0\u5934\r\n\u7ed3\u679c: 4 \u2192 3 \u2192 2 \u2192 1 \u2192 null  \u2713<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\n
\u89e3\u6cd5\u4e8c\uff1a\u9012\u5f52\uff08\u7406\u89e3\u6307\u9488\u9012\u5f52\u7684\u597d\u9898\uff09<\/h4>\n
\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
ListNode* reverseList(ListNode* head) {\r\n    \/\/ \u9012\u5f52\u7ec8\u6b62\uff1a\u7a7a\u94fe\u8868\u6216\u53ea\u6709\u4e00\u4e2a\u8282\u70b9\r\n    if (head == nullptr || head->next == nullptr)\r\n        return head;\r\n\r\n    \/\/ \u9012\u5f52\u53cd\u8f6c\u540e\u534a\u6bb5\uff0cnew_head \u662f\u53cd\u8f6c\u540e\u7684\u65b0\u5934\r\n    ListNode* new_head = reverseList(head->next);\r\n\r\n    \/\/ \u6b64\u65f6 head->next \u4ecd\u6307\u5411\u539f\u6765\u7684\u4e0b\u4e00\u4e2a\u8282\u70b9\uff08\u73b0\u5728\u662f\u53cd\u8f6c\u94fe\u8868\u7684\u5c3e\u8282\u70b9\uff09\r\n    \/\/ \u628a\u5b83\u7684 next \u6307\u56de head\uff0c\u5b8c\u6210\u6700\u540e\u4e00\u6b65\u62fc\u63a5\r\n    head->next->next = head;\r\n    head->next = nullptr;  \/\/ head \u6210\u4e3a\u65b0\u5c3e\uff0c\u65ad\u6389\u539f\u6765\u7684\u524d\u5411\u6307\u9488\r\n\r\n    return new_head;\r\n}<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u9012\u5f52\u8fc7\u7a0b\u53ef\u89c6\u5316\uff08\u4ee5 1\u21922\u21923 \u4e3a\u4f8b\uff09\uff1a<\/strong><\/p>\n
\n
\n
<\/div>\n<\/div>\n
\n
reverseList(1)\r\n  \u2514\u2500 reverseList(2)\r\n       \u2514\u2500 reverseList(3)  \u8fd4\u56de 3\uff08\u65b0\u5934\uff09\r\n          2->next->next = 2  \u5373 3\u21922\r\n          2->next = null\r\n          \u8fd4\u56de 3\r\n     1->next->next = 1  \u5373 2\u21921\r\n     1->next = null\r\n     \u8fd4\u56de 3<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u9012\u5f52\u5199\u6cd5\u601d\u8def\u4f18\u96c5\uff0c\u4f46\u8c03\u7528\u6808\u6df1\u5ea6\u662f O(n)\uff0c\u94fe\u8868\u5f88\u957f\u65f6\u6709\u6808\u6ea2\u51fa\u98ce\u9669\u3002<\/p>\n
\n
\u4e24\u79cd\u89e3\u6cd5\u5bf9\u6bd4<\/h4>\n
\n\n\n\n\n\n\n\n
<\/th>\n\u8fed\u4ee3<\/th>\n\u9012\u5f52<\/th>\n<\/tr>\n<\/thead>\n
\u65f6\u95f4<\/td>\nO(n)<\/td>\nO(n)<\/td>\n<\/tr>\n
\u7a7a\u95f4<\/td>\nO(1)<\/strong><\/td>\nO(n) \u8c03\u7528\u6808<\/td>\n<\/tr>\n
\u9762\u8bd5\u63a8\u8350<\/td>\n\u2605\u2605\u2605\u2605\u2605<\/td>\n\u2605\u2605\u2605\u2605 \u7528\u6765\u79c0\u7406\u89e3<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
\n
\u8fdb\u9636\u53d8\u4f53\uff1a\u53cd\u8f6c\u94fe\u8868 II\uff08\u529b\u6263 92 \u9898\uff09<\/h4>\n
\u53ea\u53cd\u8f6c\u7b2c left<\/code> \u5230 right<\/code> \u4f4d\u7f6e\u7684\u5b50\u94fe\u8868\uff0c\u5176\u4f59\u4e0d\u52a8\u3002<\/p>\n
\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
ListNode* reverseBetween(ListNode* head, int left, int right) {\r\n    ListNode dummy(0);\r\n    dummy.next = head;\r\n    ListNode* pre = &dummy;\r\n\r\n    \/\/ \u627e\u5230\u7b2c left-1 \u4e2a\u8282\u70b9\r\n    for (int i = 1; i < left; i++) pre = pre->next;\r\n\r\n    ListNode* curr = pre->next;\r\n    \/\/ \u7528\"\u5934\u63d2\u6cd5\"\u628a [left, right] \u6bb5\u53cd\u8f6c\r\n    for (int i = 0; i < right - left; i++) {\r\n        ListNode* next = curr->next;\r\n        curr->next = next->next;\r\n        next->next = pre->next;\r\n        pre->next = next;\r\n    }\r\n\r\n    return dummy.next;\r\n}<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u5934\u63d2\u6cd5<\/strong>\u662f\u8fd9\u9053\u9898\u7684\u7cbe\u9ad3\uff1a\u4e0d\u6539\u53d8 curr<\/code> \u6307\u9488\uff0c\u6bcf\u6b21\u628a curr<\/code> \u540e\u9762\u7684\u8282\u70b9”\u6458\u4e0b\u6765”\u63d2\u5230 pre<\/code> \u540e\u9762\uff0c\u4e00\u8d9f\u5faa\u73af\u641e\u5b9a\uff0cO(1) \u7a7a\u95f4\u3002<\/p>\n
\n
\u9762\u8bd5\u5efa\u8bae<\/h4>\n
\u8fed\u4ee3\u5199\u6cd5\u662f\u5fc5\u987b\u70c2\u719f\u4e8e\u5fc3\u7684\uff0c\u4e09\u4e2a\u6307\u9488\u7684\u6eda\u52a8\u987a\u5e8f\uff08\u5148\u5b58 next\u3001\u518d\u6389\u5934\u3001\u518d\u79fb\u52a8\uff09\u8981\u80fd\u95ed\u773c\u5199\u51fa\u6765\u3002\u9012\u5f52\u7248\u672c\u53ef\u4ee5\u4f5c\u4e3a”\u7b2c\u4e8c\u79cd\u601d\u8def”\u8865\u5145\uff0c\u5c55\u793a\u5bf9\u6307\u9488\u548c\u9012\u5f52\u7684\u6df1\u5c42\u7406\u89e3\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u529b\u6263\u7b2c 206 \u9898\u3002\u628a\u4e00\u6761\u5355\u94fe\u8868\u539f\u5730\u53cd\u8f6c<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[24],"tags":[],"class_list":["post-7397","post","type-post","status-publish","format-standard","hentry","category-value_docs"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7397","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=7397"}],"version-history":[{"count":1,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7397\/revisions"}],"predecessor-version":[{"id":7398,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7397\/revisions\/7398"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=7397"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=7397"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=7397"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}