题解 | #链表内指定区间反转#
链表内指定区间反转
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; } }