反转从位置 m 到 n 的链表_c++反转链表中m位置到n位置的元素

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

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

示例:

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

思路：首先得找到位置m和m前的节点pre，然后把m后面的节点一个接一个的插入到pre的后面去。

/**
 * 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) {
        if (head == NULL || head->next == NULL || m >= n) {
            return head;
        }
        
        ListNode s(0), *pre = &s;
        s.next = head;
        ListNode * lr = head;
        
        for (int i = 1; i < m && lr != NULL; ++i) {
            pre = pre->next;
            lr = lr->next;
        }
        for (;m < n && lr != NULL && lr->next != NULL;++m) {
            ListNode * reserve = lr->next;
            lr->next = lr->next->next;
            reserve->next = pre->next;
            pre->next = reserve;
        }
        
        return s.next;
    }
};