0092. 反转链表 II.md

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

code

好长时间没有做过链表的题竟然有点陌生。。。

比如说链表本来是：A->B->C，反转A->B很简单，就是B->next = A,同时需要将C的位置保存下来。 所以反转链表就两步：1.保存C节点；2.将B指向A。

这道题我让first一直指向第m-1个节点，second一直指向第m个节点用来保存第m个节点的位置,third遍历m到n。反转全部后，让second指向third即可。

/**
 * 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) {
        // first -> second -> third
        ListNode *h = new ListNode(0);
        h->next = head;
        ListNode *first = h, *second = head, *third = second->next;
        for(int i=0; i<m-1; i++){
            first = second;
            second = third;
            third = third->next;
        }
        for(int i=m; i<n; i++){
            ListNode* tmp = third->next;
            third->next = first->next;
            first->next = third;
            third = tmp;
        }
        second->next = third;
        return h->next;
    }
};