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

链表内指定区间反转

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

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 *
 * @param head ListNode类
 * @param m int整型
 * @param n int整型
 * @return ListNode类
 */
function reverseBetween(head, m, n) {
    const virtualHead = new ListNode(0);
    virtualHead.next = head;

    let pre = virtualHead,
        cur = null;

    // pre 前面不动的结点区域
    // 题目的结点顺序下标是从1开始的,这里需要移动到不动结点的最后一个位置,也就是m的前一个位置
    for (let i = 1; i < m; i++) {
        pre = pre.next;
    }

    // 开始需要反转的结点
    cur = pre.next;
   
    // 需要反转的循环次数
    for(let i = 0; i < n - m; i++) {
        // 利用一个临时变量完成两个结点的反转
        const temp = cur.next;
        // 当前结点指向下下个结点(跳过临时结点)
        cur.next = cur.next.next;
        
        // temp的下一个结点是前面不动结点的下一个结点(注意这里并不是cur)
        temp.next = pre.next;

        // 前面不动的区域的下一个结点是当前这个临时结点 
        pre.next = temp;

        // 经过上面的交换就完成了结点顺连,并且cur还完成了下移
    }

    return virtualHead.next;
}
module.exports = {
    reverseBetween: reverseBetween,
};

下面给出图解:

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 14:35
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 17:00
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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