題目描述

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

core code

      prev->next=cur->next;
            cur->next=head2->next;
            head2->next=cur;
            cur=prev->next;

這個地方比較繞，可以畫圖理解下，三個一組，畫一下鏈表的方向

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy(-1);
        dummy.next=head;
        ListNode *prev=&dummy;
        for(int i=0;i<m-1;++i){
            prev=prev->next;
        }
        ListNode* const head2=prev;
        prev=head2->next;
        ListNode *cur=prev->next;
        for(int i=m;i<n;++i){
//實現(xiàn)元素的反轉(zhuǎn)，同時在改變指針的方向時，同時將head-next指向最后一個元素，m后面的元素指向head ->next，在鏈表換向的同時將局部的元素的開始跟最后的元素的下一個指向進行指定
            prev->next=cur->next;
            cur->next=head2->next;
            head2->next=cur;
            cur=prev->next;
        }
        return dummy.next;
    }
};