链表反转（指定区间）_链表内指定区间反转

#include<iostream>
 
struct ListNode
{
	int value;
	ListNode *next;
	ListNode(int value, ListNode* node) : value(value), next(node)
	{
	}
};
 
ListNode * mearge(ListNode *head1, ListNode *head2)
{
	//合并后的新的有序的链表都往这个假的头上面插
	ListNode *tempHead = new ListNode(-1, nullptr);
 
	ListNode *willBeInseart = tempHead;//新元素要插在哪个节点的后面，willBeInseart始终是新链表构造过程中的最后一个节点
 
	while (head1 != NULL && head2 != NULL)
	{
		if (head1->value > head2->value)
		{
			willBeInseart->next = head2;
			head2 = head2->next;
		}
		else
		{
			willBeInseart->next = head1;
			head1 = head1->next;
		}
 
		willBeInseart = willBeInseart->next;
	}
 
	if (head1 != NULL)
	{
		willBeInseart->next = head1;
	}
	
	if(head2 != NULL)
	{
		willBeInseart->next = head2;
	}
 
	return tempHead->next;
}
 
void traverseList(ListNode *head)
{
	while (head != NULL)
	{
		std::cout << head->value << "    ";
		head = head->next;
	}
	std::cout << std::endl;
}
 
 
ListNode *reverseBetween(ListNode *oldList, int begin, int end)
{
	if (oldList == NULL) return NULL;
 
	if (begin == end) return oldList;
 
	if (begin > end)
	{
		int temp = begin;
		begin = end;
		end = begin;
	}
 
	//当链表begin是1的时候，要借助这个虚拟的头节点
	ListNode *tempDumpHead = new ListNode(-1, nullptr);
	//虚拟头节点指向了原链表的头
	tempDumpHead->next = oldList;
 
	//pre的作用是指向反转区间的begin所在节点的前一个结点，当begin为1时，pre的值就是tempDumpHead，所以用他的值初始化pre,当begin>1时，更新pre的值
	ListNode *pre = tempDumpHead;
 
	//cur的作用是指向反转区间内即将要进行反转的第一个节点，当begin为1时，cur的值就是oldList，所以用他的值初始化cur,当begin>1时，更cur的值
	ListNode *cur = oldList;
 
	//退出for循环后，pre指向的是要反转区间的前一个节点，cur指向要进行反转处理的节点，即反转区间的第一个节点
	for (int i = 0; i < begin - 1; i++)
	{
		pre = pre->next;
		cur = cur->next;
	}
 
 
 
	//反转思路是把cur指向的节点的下一个节点放到了pre的后面(pre是不动的);
 
	//比如原始链表如下：
	//1 > 2 > 3 > 4 > 5 > 6 
	 //如果begin = 2即第二个节点，end = 5即第五个节点
 
	//开始反转循环处理：
	//pre是指向第一个节点1的；cur指向第二个节点2
	//第一步：把cur指向的节点的下一个节点放到了pre的后面，结果是
	//1  3  2  4  5  6
	//此时pre仍然是指向第一个节点1的；cur指向第三个节点2
	//第二步：把cur指向的节点的下一个节点放到了pre的后面，结果是
	//1  4  3  2  5  6
	//此时pre仍然是指向第一个节点1的；cur指向第四个节点2
	//第三步：把cur指向的节点的下一个节点放到了pre的后面，结果是
	//1  5  4  3  2   6
 
	//只需要依次把反转区间内的3  4  5  依次放到pre的后面， 执行了 end - begin 即5 - 2  = 3次循环
 
	//即依次处理反转区间内的需要处理的节点，
	//只要处理end - begin个节点据可以了，
	//即使区间内有end - begin + 1 个元素，
	//但是只要end - begin个元素的位置对了，
	//区间内的反转就完成了
 
	for (int i = 0; i < end - begin; i++)
	{
		//把cur指向的节点的下一个节点放到了pre的后面(pre是不动的)
 
		//设置临时变量，保存当前需萎翻转节点的后面的节点
		ListNode *bakNode = cur->next;
 
		// 这个时候，让 temp 和 cur 两个节点翻转一下
		// 比如，一开始 i = 0 的时候 cur 为 2， temp 为 3
		// 执行完下面的代码，如果原链表是
		// 1 --> 2 --> 3 --> 4 --> 5
		// 变成了
		// 1 --> 3 --> 2 --> 4 --> 5
 
		// cur 的下一节点是等号右侧的值
		// i = 0 的时候， cur 为 2，cur.next.next 的值是 4
		// 所以，这行代码让 cur 的下一节点不是 3 ，而是 4 
		// 2 --> 4
		// 等价于 cur.next = temp.next
		cur->next = cur->next->next;
 
		// temp 的下一节点是等号右侧的值
		// i = 0 的时候， temp 为 3，pre 为 1，pre 下一节点的值是 2
		// 所以，这行代码让 temp 的下一节点不是 4 ，而是 2 
		// 3 --> 2
		bakNode->next = pre->next;
 
		// pre 的下一节点是等号右侧的值
		// i = 0 的时候， pre 为 1，temp 的值是 3
		// 所以，这行代码让 pre 的下一节点为 3
		// 1 --> 3
		pre->next = bakNode;
 
		// i = 0 结束之后，链表变成了
		// 1 --> 3 --> 2 --> 4 --> 5
	}
 
	return tempDumpHead->next;
}
 
int main()
{
	ListNode * node1 = new ListNode(1, nullptr);
	ListNode * node2 = new ListNode(2, nullptr);
	ListNode * node3 = new ListNode(3, nullptr);
	ListNode * node4 = new ListNode(4, nullptr);
	ListNode * node5 = new ListNode(5, nullptr);
	ListNode * node6 = new ListNode(6, nullptr);
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = node5;
	node5->next = node6;
 
	ListNode *head = node1;
	std::cout << "oldList" << std::endl;
	traverseList(head);
 
	ListNode *newHead = reverseBetween(head,2,5);//反转链表第2个节点到第5个节点区间的链
	std::cout << "newList" << std::endl;
	traverseList(newHead);
}