反转链表 II

问题描述

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii

思路

思路比较简单。
将反转前的链表存在一个vector tmp1中，按照题目要求对tmp1进行反转。
根据反转后的tmp1建立一个新链表。

题解

class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        int len = 0;
        if (head == nullptr) return nullptr;
        ListNode *p = head;
        vector<int> tmp1;
        ListNode *head1;
        while (p != nullptr) {
            len++;
            tmp1.push_back(p->val);
            p = p->next;
        }
        vector<int> tmp2(tmp1);
        int count = 0;
        for (int i = m-1; i <= n-1; i++) {
            tmp1[i] = tmp2[n-1 - count];
            count++;
        }
        ListNode *tmp= nullptr;
        for (int i = 0; i < len; i++) {
            if (tmp == nullptr) {
                tmp = new ListNode(tmp1[i]);
                head1 = tmp;
            } else {
                tmp->next = new ListNode(tmp1[i]);
                tmp = tmp->next;
            }
        }
        return head1;
    }
};