92. Reverse Linked List II.md

92. Reverse Linked List II

描述：难度medium。设链表第一个元素位置为1。现将位置m到n的元素反转。返回新链表的首元素指针。1 ≤ m ≤ n ≤ length。

1. 思路
2. 实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode *head, int m, int n) {
        int i;
        ListNode * dummy = new ListNode(0);   //加一个头指针dummy
        ListNode * p = dummy;
        dummy->next = head;        
        for(i=1; i<m; i++)
        {
            p = p->next;    //循环结束时，p在位置m-1（head位置是1）
        }
        ListNode * piv = p->next;   //piv在位置m
        
        for(i=m; i<n; i++)
        {
            swap(p->next, piv->next->next);
            swap(p->next, piv->next);
        }
        return dummy->next;
}
};