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

链表内指定区间反转

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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
       ListNode dummy = new ListNode(-1);
       ListNode left = dummy;
       ListNode cur = dummy;
       dummy.next = head;
       for(int i = 0;i < n;i++){
            if(i < m - 1){
                left = left.next;
            }
            cur = cur.next;
       }
       ListNode right = cur.next;
       ListNode subHead = left.next;
       // 将原链表断开
       left.next = null;
       cur.next = null;
       left.next = reverse(subHead);
       subHead.next = right; 
       return dummy.next;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = cur.next;
        while(next != null){
            cur.next = pre;
            pre = cur;
            cur = next;
            next = next.next;
        }
        cur.next = pre;
        return cur;
    }
}

解题思路:

  • 找到三个节点,即子链表前一个节点记为left,以及子链表末尾的后一个节点以及子链表头部
  • 将原链表断开、子链表反转
  • 重新连接
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-25 17:46
点赞 评论 收藏
分享
07-29 14:46
门头沟学院 Java
码农索隆:好了,我说句公道话,咱三都辛苦了
点赞 评论 收藏
分享
06-17 00:26
门头沟学院 Java
程序员小白条:建议换下项目,智能 AI 旅游推荐平台:https://github.com/luoye6/vue3_tourism_frontend 智能 AI 校园二手交易平台:https://github.com/luoye6/vue3_trade_frontend GPT 智能图书馆:https://github.com/luoye6/Vue_BookManageSystem 选项目要选自己能掌握的,然后最好能自己拓展的,分布式这种尽量别去写,不然你只能背八股文了,另外实习的话要多投,尤其是学历不利的情况下,多找几段实习,最好公司title大一点的
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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