92. Reverse Linked List II.md

92. Reverse Linked List II

思路

首先还是开辟一个真正的头结点real_head, 其next指针指向head。然后向后移动m - 1步到达需要翻转的第一个节点的前一个节点，记为pre，如果按照下面的例子的话 pre就指向1，然后我们翻转pre后面的n-m个节点即可。

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

C++

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode *real_head = new ListNode(0);
        real_head -> next = head;
        ListNode *p, *pre = real_head, *tmp;
        n -= m;
        while(--m) pre = pre -> next;
        p = pre -> next;
        
        // reverse n-m nodes
        while(n--){
            tmp = p -> next;
            p -> next = tmp -> next;
            tmp -> next = pre -> next;
            pre -> next = tmp;   
        }
        return real_head -> next;
    }
};