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

链表内指定区间反转

https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c

/**
 * 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 (head == nullptr) {
            return nullptr;
        }


        // m和n判断
        if (m <= 0 || m > n ) {
            return nullptr;
        } else if (m == n) {
            return head;
        } else { // 0 < m < n
            // 为了方便,在链表前加一个头节点pre_head
            ListNode* pre_head = new ListNode(-1);
            pre_head->next = head;

            // 指针
            ListNode* mPre = pre_head;      // 保存第m-1个节点
            for (int i = 0; i < m - 1; i++) {
                mPre = mPre->next;
            }
            ListNode* mPtr = mPre->next;     // 保存第m个节点,待取待插节点前一个节点
            ListNode* tmp = mPtr->next;      // 待取待插节点

            for (int i = m; i < n &&
                    tmp != nullptr; i++) {  // 此时可能出现n>size的情况
                mPtr->next = tmp->next;     // 取下
                tmp->next = mPre->next;     // 前插
                mPre->next = tmp;
                tmp = mPtr->next;           // tmp更新,mPtr不变
            }

            return pre_head->next;
        }

        return head;
    }
};

全部评论

相关推荐

昨天 11:07
门头沟学院 Java
点赞 评论 收藏
分享
码农索隆:想看offer细节
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务