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

链表内指定区间反转

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类
     */
     //本题难点:空指针问题和控制反转区间
     //可以加入头结点来解决反转区间的问题(主要是解决从head到n区间的问题)
     //思路:先找到反转区间的前一个结点和末尾的后一个结点,方便连接
     //然后对反转区间进行迭代头插法(注意控制次数),最后进行连接。
     //时间O(N),空间O(1)
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if(m==n) {
            return head;
        }
        ListNode Head=new ListNode(-1);
        ListNode head1=Head;//分别记录区间的前一个,和末尾的后一个
        ListNode tail1=head;
        Head.next=head;
        int n1=n;
        int m1=m-1;
        while(m1>0) {
            head1=head1.next;
            m1--;
        }
        while(n1>0) {
            tail1=tail1.next;
            n1--;
        }
        ListNode head2=null;//反转区间的头结点
        //cur和tmp用来迭代
        ListNode cur=head1.next;
        ListNode tmp=cur;
        int num=n-m+1;
        while(num>0) {
            tmp=cur.next;
            if(head2==null) {
                head2=cur;
                cur.next=tail1;
            }
            else {
                cur.next=head2;
                head2=cur;
            }
            cur=tmp;
            num--;
        }
        if(head1!=null)
        head1.next=head2;
        return Head.next;
    }
}

全部评论

相关推荐

冲芭芭拉鸭:你这图还挺新,偷了。
投递美团等公司10个岗位
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务