力扣-92-反转链表Ⅱ

其实对链表的考察就是考察指针，不喜欢Java写算法题的一大原因就是Java没有指针

区间反转链表，相对于整体反转链表而言
回忆一下链表的整体反转，大概是两种做法

1. 递归，从后往前处理
2. 迭代，用三个指针（修改原指针的话只需要两个额外的）
   这里感觉用迭代更直观容易些，回顾一下迭代是怎么反转链表的
   

	ListNode* pre = nullptr, * cur = head;// 初始化pre为空指针，因为头反转后指向为空
			nxt = cur->next;// 先保存下一个节点
			cur->next = pre;// 修改节点指针指向上一个节点
			pre = cur;
			cur = nxt;

不完全是那么简单，尽管只反转其中一段，但这一段前后的两个指针也需要改变

头节点反转不一定指向空
而如果是left=1或者是right=0，就没有

感觉如果用迭代的话，需要额外保存反转段的前一个节点和后一个节点，而且这两个节点可能为空
想要一趟趟遍历迭代难点就在于反转段前后指针的处理，这两个指针不一定存在
如果想要保存这两个指针，怎么初始化保存也很麻烦

瞄一眼题解了
第一次完成功能的实现

ListNode* reverse(ListNode* head) {
	// 这里的head不能改，后面要用
	// left可能==right，参数判断放到前面去
	ListNode* pre = nullptr,*cur = head,*nxt;

	while (cur) {
		nxt = cur->next;
		cur->next = pre;
		pre = cur;
		cur = nxt;
	}
	return pre;
}

ListNode* reverseBetween(ListNode* head, int left, int right) {
	ListNode* dummyHead = new ListNode(-1);
	dummyHead->next = head;// 使用虚拟头节点避免是否为空的分类讨论
	// 但是这里不需要虚拟尾节点？

	ListNode* preNode = dummyHead;
	// 这里不需要额外的count遍历+while，可以控制for循环此时
	for (int i = 0; i < left - 1; i++) preNode = preNode->next;
	// 让preNode指向区间的前一个节点

	ListNode* rightN = preNode;
	for (int i = 0; i < right - left + 1; i++) rightN = rightN->next;
	// 让rightN指向区间右侧的节点

	// succNode当然可能为空，但是它只会被指向而不是指向别人，送一不会出翔空指针异常，所以不需要虚拟尾节点
	ListNode* leftN = preNode->next, *succNode = rightN->next;// 这里保存succNode是因为rightN->next会被修改

	rightN->next = nullptr;// 把区间右节点置空是为了区间反转的结束条件，也是保证正常反转
	preNode->next = reverse(leftN);
	leftN->next = succNode;// 反转后leftN变成了反转区间的最后一个节点

	return dummyHead->next;// 这里不能是返回head，因为head可能是反转段的一部分，会变化
	// 那为什么dummy->next可以？当head作为被反转区间的第一个节点，dummyHead就是preNode，所以dummyHead->next其实是被更新了的
}

所以我之前是被卡在了哪里？
首先就是关于反转段前后两个节点，可能为空和可能不空的情况讨论复杂想不明白，当然也想到了虚拟头，但是没想明白为什么不需要虚拟尾
另外就是多此一举了一个计数count，本可以通过for循环控制次数

但是它这里并不能算是顺序一次遍历，第一趟只遍历到right，后来反转反向遍历right-left+1
也就是总时间复杂度O(2right-left+1)，当left=1,right=n，就相当于整个链表反转，复杂度会退化到O(2N)

再者就是区间反转时的指针操作，包括一个指针置空，以及反转子函数中不能修改原指针（不然原指针会变成空指针），当然这一块儿可能还有优化的空间

迭代写法应该是比递归更清晰的，下次就应该考虑递归的写法了，另外题解中还有一种插入的写法