• 《算法通关村第二关——指定区间反转问题解析》


    《算法通关村第二关——指定区间反转问题解析》

    题目描述

    给你单链表的头指针head和两个整数left和right,其中left <= right 。 请你反转从位置left到位置right的链表节点,返回反转后的链表。

    示例1:
    输入: head = [1,2,3,4,5],left = 2, right = 4
    输出: [1,4,3,2,5]
    
    • 1
    • 2
    • 3

    头插法

    通过一个一个插入前面进行反转。

    在这里插入图片描述

    代码:

    /**
     * 头插法指定区间反转
     * @param head
     * @param start就是题中的left
     * @param end 题中的right
     * @return
     */
    public static LinkedNode ReverseSpecificInterval1(LinkedNode head , int start,int end){
        // 设置dummyNode 是这类问题的一般解法
        LinkedNode dummyNode = new LinkedNode(-1);
        dummyNode.setNext(head);
        LinkedNode pre = dummyNode;
        for(int i = 0 ; i < start - 1 ; i++){
            pre = pre.getNext();
        }
        LinkedNode cur = pre.getNext();
        LinkedNode next = null;
        for(int i = 0 ;i < end-start ; i++){
            next = cur.getNext();
            cur.setNext(next.getNext());
            next.setNext(pre.getNext());
            pre.setNext(next);
        }
        return dummyNode.getNext();
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    穿针引线法

    通过把指定区间提取出来,然后进行反转,最后再接回原链表的方法。

    在这里插入图片描述

    上代码:

    /**
         * 穿针引线
         * @param head
         * @param start
         * @param end
         * @return
         */
        public static LinkedNode ReverseSpecificInterval2(LinkedNode head,int start , int end){
            // 因为头节点可能发生变化,使用虚拟头节点可以便面复杂的分类讨论
            LinkedNode dummyNode = new LinkedNode(-1);
            dummyNode.setNext(head);
            LinkedNode pre = dummyNode;
            // 第一步,从虚拟头节点走start-1步,来到start节点的前一个结点。
            for ( int i = 0 ; i < start -1 ; i++){
                pre = pre.getNext();
            }
            // 第二步,从pre 再走end-start+1步来到end节点
            LinkedNode endNode = pre;
            for(int i = 0 ; i  < end-start+1 ; i++){
                endNode = endNode.getNext();
            }
            // 第三步切出一个子链
            LinkedNode startNode = pre.getNext();
            LinkedNode succ = endNode.getNext();
            endNode.setNext(null);
            // 第四步反转链表
            reverseLinkedList(startNode);
            // 第五步,接回原来的链表
            pre.setNext(endNode);
            startNode.setNext(succ);
            return dummyNode.getNext();
        }
    
        private static void reverseLinkedList(LinkedNode startNode) {
            LinkedNode pre = null ;
            LinkedNode cur = startNode;
            while(cur != null){
                LinkedNode next = cur.getNext();
                cur.setNext(pre);
                pre = cur;
                cur = next;
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    近期在自学 Java 做项目,加入了一个编程学习圈子,里面有编程学习路线和原创的项目教程,感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑,也希望能对大家有帮助,扫 ⬇️ 二维码即可加入。

    在这里插入图片描述

    也可以点击链接:我正在「编程导航」和朋友们讨论有趣的话题,你⼀起来吧?

  • 相关阅读:
    Linux系统编程--IO
    机器学习基础-数据分析:房价预测
    通关GO语言13 参数传递:值、引用及指针之间的区别?
    Openssl数据安全传输平台007:共享内存及代码的实现 ——待完善项目具体代码和逻辑
    阿里云发送验证码流程
    deepspeed 训练多机多卡报错 ncclSystemError Last error
    免费的云产品
    大数据知识合集之预处理方法
    【疑难】使用ARM development studio仿真 error:Failed to create Jython interpreter
    C++基础:数据结构 代码模板
  • 原文地址:https://blog.csdn.net/Go_ahead_forever/article/details/133945229