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

链表内指定区间反转

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

方法

  1. 找到反转区间的首尾地址[pos_m, pos_n],并记录左边界的前一个位置pre_m,右边界的后一个位置next_n
  2. 单独反转区间,返回反转后的链表首地址pp(反转函数内部以及将反转后的链表尾部指向next_n了)
  3. 进行拼接:pre_m-<next = pp; (pp尾部的拼接在2中已经做好了)
  4. 需要注意的是当pos_m就是链表尾部的时候,直接返回pp即可,不用拼接前面(也拼接不了,此时pre_m为nullptr)
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseList(ListNode *low, ListNode *high, ListNode *tail) {
        ListNode *pre = tail;
        ListNode * cur = low;
        while (cur != high) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
    
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // write code here
        ListNode *pre_m = nullptr;
        ListNode *pos_m = head;
        ListNode *pos_n = head;
        ListNode *next_n = nullptr;
        while (pos_m && m > 1) {
            pre_m = pos_m;
            pos_m = pos_m->next;
            m--;
        }
        while (pos_n && n > 1) {
            pos_n = pos_n->next;
            n--;
        }
        next_n = pos_n->next;
        ListNode *pp = reverseList(pos_m, pos_n->next, next_n);
        if (pre_m == nullptr){
            return pp;
        }else {
            pre_m->next = pp;
        }
        return head;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-03 17:37
点赞 评论 收藏
分享
06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
这算盘打的
程序员小白条:都这样的,都是潜规则,你自己说可以实习一年就行了,实习可以随便跑路的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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