题解 | #反转部分单向链表#

思路一：利用我们的正常思维，将需要翻转的那部分拆解下来，然后再将翻转后的链表链接上

#include <iostream>
using namespace std;

struct ListNode
{
	int val;
	ListNode* next;

	ListNode(int x)
		: val(x)
		, next(nullptr)
	{}
};

// 初始化链表  --  尾插法
ListNode* init_list()
{
	int n = 0, val = 0;
	ListNode* dummy = new ListNode(-1); // 创建虚拟结点，保证第一个结点插入的时候cur值不为空，否则需要进行特判处理
	ListNode* cur = dummy;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> val;
		ListNode* newnode = new ListNode(val);
		newnode->next = NULL;
		cur->next = newnode;
		cur = newnode;
	}

	return dummy->next;
}

// 反转链表
ListNode* reverse(ListNode* head)
{
	ListNode* prev = NULL;
	ListNode* cur = head;
	while (cur)
	{
		ListNode* tmp = cur->next;
		cur->next = prev;
		prev = cur;
		cur = tmp;
	}

	return prev;
}

ListNode* reverseLR(ListNode* head, int L, int R)
{
	// 创建虚拟结点是为了更加方便的返回头结点，假如我们需要从第一个位置开始反转，那么我们要记录第一个位置的前一个位置并且头结点会发生更换，所以这里添加一个虚拟结点我们就能够很好的达到目的，也不需要关心头结点的变化，返回它的next即可
	ListNode* dummy = new ListNode(-1);
	dummy->next = head;
    // pHead为L的位置，pTail为R的位置
	ListNode* pHead = head, * pTail = NULL;
    // prevNode为L的前一个位置，nextNode为R的后一个位置
	ListNode* prevNode = dummy, *nextNode = NULL;

	// 第一步：找到L位置的结点以及前一个节点
	for (int i = 0; i < L - 1; i++)
	{
		prevNode = pHead;
		pHead = pHead->next;
	}
	// 第二步：找到R位置的结点以及后一个节点
	pTail = pHead;
	for (int i = 0; i < R - L; i++)
	{
		pTail = pTail->next;
	}
	nextNode = pTail->next;
	// 第三步：断开链接
	pTail->next = NULL;
	// 第四步：反转[L, R]区间的链表
	ListNode* ppNode = reverse(pHead);

	// 第五步：恢复链接
	// 这里注意了反转链表之后原来的头结点此时变为了尾结点，所以应用pHead链接到nextNode结点
	prevNode->next = ppNode;
	pHead->next = nextNode;

	return dummy->next;
}

int main()
{
	ListNode* phead = init_list();  
	int L = 0, R = 0;
	cin >> L >> R;
	ListNode* head = reverseLR(phead, L, R);
	while (head)
	{
		cout << head->val << " ";
		head = head->next;
	}
	cout << endl;

	return 0;
}

思路二：思路一的弊端：假设需要反转的链表部分,占比比较大,则需要两次遍历链表来实现(1.遍历确定反转链表的起始位置 2.遍历链表进行反转). 那是不是可以考虑一次遍历链表就解决该问题呢? 这里的思路是:采用头插的方式一次遍历解决问题。

下面给出核心代码：

ListNode* reverseLR(ListNode* head, int L, int R)
{
	ListNode* dummy = new ListNode(-1);
	dummy->next = head;
    // pHead为L的位置
	ListNode* pHead = head;
    // prevNode为L的前一个位置
	ListNode* prevNode = dummy;

	// 第一步：找到L位置的结点以及前一个节点
	for (int i = 0; i < L - 1; i++)
	{
		prevNode = pHead;
		pHead = pHead->next;
	}

	// 第二步：重复R-L次头插
    for (int i = 0; i < R - L; i++)
    {
    	// nextNode为L的后一个位置
        ListNode* nextNode = pHead->next;
        pHead->next = nextNode->next;
        nextNode->next = prevNode->next;
        prevNode->next = nextNode;
    }

	return dummy->next;
}