题目
将一个节点数为 size 链表 m 位置到 n位置之间的区间反转,
要求时间 复杂度 O(n),空间复杂度 O(1)。
例如: 给出的链表为1→2→3→4→5→NUL,m=2,n=4
返回1→>4→>3→2->5->NULL
, 数据范围:链表长度0< size < 1000,0 <m<n< size,链表 中每个节点的值满足 val < 1000
空间复杂度 O(n) 要求:时间复杂度 O(n), 进阶:时间复杂度 O(n),空间复杂度 O(1)
来自牛客网
解析
目的反转一个给定链表中从位置m到n的字链表。
1.首先,创建一个虚拟头节点dummy,它的next指向head。这样做的目的是在反转过程中保持原始头节点不变,方便最后返回结果。
2.初始化一个指针prev指向dummy,用于遍历过程中纪录前一个节点。
3.循环遍历
4.检查prev是否为null
5.定义start为反转子链表的起始节点,then为start的下一个节点
6.循环遍历n-m次
start的next的指针指向then的下一个节点
then的next的指针指向prev的next
prev的next指针为then
then为start的next
7返回。
代码
import java.util.*
class ListNode{
int val;
ListNode next;
ListNode next;
ListNode(int val){
this.val=val;
}
}
public class Solution{
public ListNode reverseBetween(ListNode head ,int m,int n){
if(head == null || m>=n){
return head;
}
ListNode dummy =new ListNode(-1);
dummy.next =head;
ListNode prev =dummy;
//找到要反转区间的前一节点
for(int i=0;i<m-1&&prev!=null;i++){
prev=prev.next;
}
if(prev==null || prev.next==null){
return head;
}
ListNode start=prev.next;
ListNode then=start.next;
//开始反转区间
for(int i=0;i<n-m;i++){
start.next=then.next;
then.next=prev.next;
prev.next =then;
then =start.next;
}
return dummy.next;
}
}
总结
不断练习