题解 | #链表内指定区间反转#
链表内指定区间反转
http://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
1、一次遍历，头插法：时间复杂度O(n),空间复杂度O(1)
思路：一个指针A定位到起始点的前一个位置，另外一个指针B定位到起始点W，B指针不停向后移动，遇到一个插到A与W之间
有人会问，如果起点是1，那它的前一个位置怎么办呢？
那么为了防止这种情况出现，那在链表前加一个哨兵就能解决这样的情况
public ListNode reverseBetween (ListNode head, int m, int n) {
if(head==null||head.next==null){
return head;
}
//哨兵
ListNode numpy = new ListNode(-1);
numpy.next = head;
// write code here
ListNode nodePre = numpy;
int k = m;
//将nodePre定位在交换的起点的前一个位置上
while(k>1){
nodePre = nodePre.next;
k--;
}
//定位nodeNext为交换的起点上
ListNode nodeNext=nodePre.next;
ListNode remove;
while(n-m>0){
//如试例：1，2，3，4，5；此时，nodePre=1；nodeNext=2；那remove是3
remove = nodeNext.next;
//这一步让2指向4，也就是断开3的连接
nodeNext.next=nodeNext.next.next;
//这一步就是让3指向2，因为nodepre是1
remove.next = nodePre.next;
//这一步就是让1指向3
nodePre.next = remove;
n--;
}
return numpy.next;
}
2、两次遍历：时间复杂度O(n),空间复杂度O(1)
需要遍历两次：第一次定位起点的前一个位置A，第二次定位到反转区间的最后一个位置B，A.next和B之间的链表进行反转
反转的结果用A+ 反转结果 +B.next
if(head==null||head.next==null){
return head;
}
ListNode numpy = new ListNode(-1);
numpy.next = head;
// write code here
ListNode nodePre = numpy;
ListNode nodeNext = numpy;
//定位反转区间的结束位置
//因为题目说了，不需要考虑长度不够的情况，所以nodeNext！=null可以不用
while(nodeNext!=null&&n>0){
nodeNext=nodeNext.next;
n--;
}
if(n>0){
return head;
}
//定位反转区间起点的前一个位置
while(nodePre!=null&&m>1){
nodePre=nodePre.next;
m--;
}
//记录前一个位置
ListNode pre = nodePre;
//找到起点
nodePre = nodePre.next;
//找到翻转区间后的下一段起点
ListNode next = nodeNext.next;
//断开与之的联系
nodeNext.next =null;
//反转链表
ListNode reverseNode = reverse(nodePre);
//拼接
pre.next = reverseNode;
//注意反转后的区间尾点是之前的起点
nodePre.next = next;
return numpy.next;
}
public ListNode reverse(ListNode node){
ListNode pre = null;
while(node!=null){
ListNode temp = node.next;
node.next = pre;
pre = node;
node=temp;
}
return pre;
}
查看28道真题和解析
