leetcode日记（79）反转链表Ⅱ

链表的题都挺简单的。

使用一趟扫描就可以实现，不过要记录的中途节点有点多，需要记录left的前一个、left所在的元素，循环中要记录三个元素，每次循环第二个元素指向第一个元素，随后三个元素向后移动。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left==right) return head;
        ListNode *h = new ListNode(0,head);
        ListNode *result=h;
        for(int i=0;i<left-1;i++) h=h->next;
        ListNode *hh=h->next;
        ListNode *a=hh->next;
        ListNode *b=a->next;
        a->next=hh;
        ListNode* c=a;
        for(int i=left;i<right-1;i++){
            c=a;
            a=b;
            b=b->next;
            a->next=c;
        }
        h->next=a;
        hh->next=b;
        return result->next;
    }
};

链表题目都需要注意，在开始时最好设一个“开始的开始”在head前面，这样就会方便很多。