题解 | 链表内指定区间反转

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <bits/types/struct_tm.h>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        if (n <= m || n <= 0 || m <= 0) return head;
        auto new_H = new ListNode(0);
        new_H->next = head;
        int idx = 0;
        ListNode *pre = new_H, *cur = head, *start;
        while (idx < n) {
            ++idx;
            if (idx == m) start = pre;
            else if (idx > m) {
                ListNode *tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
                continue;
            }
            pre = cur;
            cur = cur->next;
        }
        start->next->next = cur;
        start->next = pre;
        return new_H->next;
    }
};

题干分析:

题目要求我们对一个链表指定的区间对该区间内的节点进行反转操作.

算法思路:

与链表相关的操作使用语言描述很难描述清楚,因此见图:

开始:

在未开始进行反转前:

找到第一个需要反转的节点并记录前一个节点位置:

开始反转

移动指针,准备下次反转

循环判断时idx=4,5时循环操作与idx=3几乎一致,因此省略,只展示idx=6.

跳出循环:(勘误:此时tmp指针生命周期已尽,画图时忘删了.)

连接首尾:

复杂度分析:

全过程最多遍历n个节点,时间复杂度为O(n);

全过程只使用到了常数额外空间(tmp指针每次使用后均会被系统回收),空间复杂度为O(1).