leetcode92. 反转链表 II

题目

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

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

示例:

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

思路

与反转链表类似，单要注意边界条件
leetcode92. 反转链表 II

实现

/**
 * 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 || !head->next) {
            return head;
        }
        int count = 0;
        // base是第m-1个节点，用来插入
        // first是第m个节点，用来衔接第 n+1个节点
        ListNode* base = nullptr;
        ListNode* vir = new ListNode(0);
        vir->next = head;
        ListNode* a = nullptr;
        if (m == 1) {
            base = vir;
        }
        while (head && count < n) {
            ++count;
            if (count == (m - 1)) {
                base = head;
                head = head->next;
            } else if (count == m) {
                first= head;
                head = head->next;
            } else if (count > m && count <= n) {
                ListNode* tmp = head->next;
                head->next = base->next;
                base->next = head;
                head = tmp;
            } else {
                  head = head->next;
            }
          
        }
        first->next = head;
        return vir->next;
    }
};