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

链表内指定区间反转

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

  • 1、针对只有一个节点时,或者反转区间差为0时,直接信任传入链表头节点(不对头节点判空),返回头节点

  • 2、针对只有两个节点时,反转区间开始位置必定为1,且反转后,表尾成为新的表头,故需要将表头指向原表尾,返回新表头

  • 3、针对多节点,反转区间差大于等于1的,首先遍历寻找到区间开始节点,保存开始节点前一个节点,用于指向反转后区间的开始节点,另外需要保存开始遍历的节点,用于反转完成后的重新连接链表后续节点,即start = cur,然后开始遍历区间,开始进行反转,反转期间,需要保存一个临时节点tnx,表示当前节点下一节点,然后将当前节点指向前一节点pre(初始为null),再将pre指向当前节点cur,最后,将当前节点指向下一节点tnx,区间索引加1,在区间结束后,重新连接区间原开始反转节点的后续节点(第一次反转时,开始节点的后续节点被置空了),此时遍历完成后当前节点为区间外后续第一个节点,即start.next = cur;

  • 4、思路:

    4.1反转

    4.2重新连接 alt

  • 5、实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if(head.next == null || m == n){
            return head;
        }
        int tm = 1;
        ListNode cur = head;
        ListNode ppre = null;
        while(tm < m){
            ppre = cur;
            cur = cur.next;
            tm++;
        }
        ListNode start = cur;
        ListNode pre = null;
        while(tm <= n){
            ListNode tnx = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tnx;
            tm++;
        }
        if(ppre != null){
            ppre.next = pre;
        }
        if(m == 1){
            head = pre;
        }
        if(cur != null){
            start.next = cur;
        }
        return head;
        
    }
}
``
全部评论

相关推荐

看到这个内容真是闹麻了。。。。。。现在有了AI以后很多人面试都会作弊吗?&nbsp;那对老老实实面试的人岂不是不公平....
程序员牛肉:公平那是对小孩子讲的童话故事,成年人的世界只有能不能接受失败的后果。 你要是能接受面试作弊被发现之后多家公司联合永久拉黑的后果,你就搞。
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
下个早班:秒挂就是不缺人
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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