算法通关村第二关——指定区间反转问题解析-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第二关——指定区间反转问题解析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

指定区间反转：

Leetcode92有这样一道题：给你单链表的头指针head和两个整数left、right，其中left<=right，请你反转从位置left到位置right的链表结点，返回反转后的链表，如图所示：

算法通关村第二关——指定区间反转问题解析,算法

这道题呢，有两种不同的解法，分别是头插法和穿针引线法，头插法就是我们前面说过的带头结点的反转，而穿针引线法就是不带头结点实现反转的方法，接下来我将逐一介绍：

1.头插法：

前面我们说过带头结点的反转有两个重点要求：1.虚拟头结点 2.拆拆拆

熟练掌握以上两个思想后，这道题的解决将变得十分简单。在这道题中，我认为我们可以将区间前的第一个结点看作虚拟头结点，而区间内除第一个结点以外的全部结点则需要逐一拆除并进行插入，如下图所示：

算法通关村第二关——指定区间反转问题解析,算法

我们可以建立一个cur指针始终指向区间的第一个元素，之后的每一步操作我们需要以下几个步骤：1.找到当前结点的下一个结点 2.拆除：令cur指针指向的结点指向next结点的下一个结点（即：将next指针指向的结点“拆下”，并保存后一个结点的位置）3.插入：令next指针指向的结点指向虚拟头结点的下一个结点（这里的虚拟头结点就是我们说的区间前的第一个结点） 4：令虚拟头结点指向next指针所指向的结点。重复上述操作，即可实现区间反转，代码如下：

// 头插法
struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
{
	struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));//开辟一个虚拟的头结点
	dummy->val = -1;
	dummy->next = head;//令虚拟头结点的下一个结点指向真实头结点
	struct ListNode* ans = dummy;//创建一个指针用来遍历链表
	for (int i = 0; i < left - 1; i++)
	{
		ans = ans->next; //找到指定区间的前一个元素
	}
	struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode));
	cur = ans->next;//令cur为区间的第一个结点，并始终保持不变
	for (int i = 0; i < right - left; i++)//遍历整个区间
	{
		struct ListNode* next = cur->next;//首先找到当前结点的下一个结点
		cur->next = next->next;//令当前结点的下一个结点指向下一个结点所指向的结点，即将next结点“拆下”
		next->next = ans->next;//令next结点的下一个结点指向区间前的结点所指向的结点
		ans->next = next;//令区间前的结点指向next结点
	}
	return dummy->next;
}

2.穿针引线法：

如果说第一种方法的特点是拆拆拆，那这一种方法的特点就类似于从整体上解决问题的方法，让我们先从图片中了解大致思想：

算法通关村第二关——指定区间反转问题解析,算法

这种方法呢，其实就是将整个区间先与原链表脱离，单独将区间反转之后再接入原链表，步骤如下：1.找到区间的前驱结点与后续结点，便于之后进行连接 2.定位区间的左结点与右结点 3.将整个区间拆下 4.对区间进行反转 5.将反转后的区间接入旧链表，代码如下：文章来源地址https://www.toymoban.com/news/detail-620587.html

//反转链表
void reverseList(strruct ListNode* head)
{
	sturct ListNode* pre = NULL;
	struct ListNode* cur = head;
	while (cur != NULL)
	{
		struct ListNode* next = cur->next;
		cur->next = pre;
		pre = cur;
		cur = next;
	}

}
//穿针引线法
struct ListNode* reverseBetween(struct ListNode* head, int left, int right)
{
	struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
	dummy->val = -1;
	dummy->next = head;
	struct ListNode* pre = dummy;
	for (int i = 0; i < left - 1; i++)
	{
		pre = pre->next;//首先找到区间的前一个结点
	}
	struct ListNode* rightNode = pre;
	for (int i = 0; i < right - left + 1; i++)
	{
		rightNode = rightNode->next;//令该结点指向区间的最后一个结点
	}
	struct ListNode* leftNode = pre->next;//找到区间的第一个结点
	struct ListNode* succ = rithtNode->next;//找到区间之后的第一个结点
	rightNode->next = NULL;
	pre->next = NULL;//断开区间链表与原链表的链接
	reverseList(leftNode);//将区间内的链表进行反转
	pre->next = rightNode;//令之前保存的区间前的第一个结点指向此时链表的头结点
	leftNode->next = succ;//令链表的尾结点指向之前保存的区间之后的第一个结点
	return dummy->next;
}

到了这里，关于算法通关村第二关——指定区间反转问题解析的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！