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

链表内指定区间反转

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

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) {
        if(head == null || head.next == null || m==n){
            return head;
        }

        //创建一个虚节点
        ListNode dummy = new ListNode(-1);
        dummy.val = -1;
        dummy.next = head;

        //m位置的前一个节点
        ListNode ll = dummy,lr ,rl = dummy,rr;
        for(int i = 0; i< m-1; i++){
            ll = ll.next;
        }
        //m位置的节点
        lr = ll.next;

        //n位置的节点
        for(int i = 0; i< n; i++){
            rl = rl.next;
        }
        //n后一个节点
        rr = rl.next;

        rl.next = null;
        reverse(lr);
		
	  	//把反转后的连接起来
        ll.next = rl;
        lr.next = rr;

        return dummy.next;
    }

    public static void reverse(ListNode head){
        if(head == null){
            return;
        }

        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
    }
}

全部评论

相关推荐

待现的未见之事:起码第一句要把自己的优势说出来吧。比如什么xx本27届学生,随时到岗....
点赞 评论 收藏
分享
04-14 20:10
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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