链表指定区间反转解题思路

题目要求时间复杂度 O(n)O(n)，空间复杂度 O(1)

定义三个指针变量*pre,*left,*right;

1. pre,找到待反转链表的前一个节点
2. left待反转链表的第一个节点
3. right待反转链表的第二个节点

链表反转的逻辑如下

1. 断开第一个节点和第二个节点
2. 改变第一个节点和第二个节点的指向
3. 将前一个节点和第二个节点连接
4. 更新right

struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {
   if(head==NULL||m=n){
	return head;
}
  struct ListNode dummy;
  dummy.next=head
 struct ListNode *pre = &head;
  for(int i=1;i<m;i++){
	pre = pre->next;
  }
  struct ListNode *left = pre->next;
  struct ListNode *right = lift->next;
  for(int i=0;i<n-m;i++){
	left->next=right->next;
	right->next=pre->next;
	pre->next = right;
	right= left->next;
  }
  return dummy.next;
}