反轉從位置 m 到 n 的鏈表，請使用一趟掃描完成反轉， 說明: 1 ≤ m ≤ n ≤ 鏈表長度， 示例: 輸入: 1->2->3->4->5->NULL, m = 2, n = 4 輸出: 1->4->3->2->5->NULL 來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/reverse-linked-list-ii 著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處， 尋找關鍵的節點
找到開始逆置的節點，記錄該節點的前驅和該節點
從 head 開始，逆置 change_len = n-m+1 個節點
將 pre_head 與 new_head連接，modify_list_tail 與 head 連接
1 struct ListNode { 2 int val; 3 ListNode *next; 4 ListNode(int x) : val(x), next(NULL) {} 5 }; 6 7 class Solution { 8 public: 9 ListNode* reverseBetween(ListNode* head, int m, int n) { 10 int change_len = n - m + 1; 11 ListNode *pre_head = NULL;//需要逆置的頭節點的前驅 12 ListNode *result = head; 13 14 while (head && --m) {//m-1 次 15 pre_head = head;//記錄當前頭節點 16 head = head->next; 17 }//head >>需要逆置的頭節點 18 ListNode *modify_list_tail = head;//記錄初始逆置的頭節點，也就是逆置后的尾部 19 ListNode *new_head = NULL;//逆置后的頭節點 20 while (head && change_len) { 21 ListNode *next = head->next; 22 head->next = new_head; 23 new_head = head; 24 head = next;//最后一次 head 指向逆置段的后一個節點 25 --change_len;//只逆置 change_len 個節點 26 } 27 modify_list_tail->next = head;//逆置段的尾部指向下一個節點 28 if (pre_head) { 29 pre_head->next = new_head;//逆置段的前一個節點指向 30 } else { 31 // pre_head = new_head; ? 32 // 特殊情況： m=1 從第一個節點開始逆置，result存放的就是頭節點，所以 result 需要變成逆置后的頭節點 33 result = new_head; 34 } 35 return result; 36 } 37 };
測驗
1 int main(int argc, const char * argv[]) { 2 ListNode a(1); 3 ListNode b(2); 4 ListNode c(3); 5 ListNode d(4); 6 ListNode e(5); 7 a.next = &b; 8 b.next = &c; 9 c.next = &d; 10 d.next = &e; 11 Solution solve; 12 ListNode *head = solve.reverseBetween(&a, 2, 4); 13 while (head) { 14 cout <<head->val<<endl; 15 head = head->next; 16 } 17 18 return 0; 19 }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127155.html
標籤：其他
上一篇：初探 jQuery