面试经典150题 P92 反转链表 II

---

时间轴

2025-11-20

init

---

题目：

P92 反转链表 II

https://leetcode.cn/problems/reverse-linked-list-ii/description/?envType=study-plan-v2&envId=top-interview-150

链表的题目中一般不能直接更改结点的值。
使用头插法反转链表，创建一个虚拟头节点会避免一些特殊情况，另外最后不能返回head，而是virt_head->next，因为head可能会因为交换而发生变化。

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

class Solution {
    public:
	ListNode *reverseBetween(ListNode *head, int left, int right)
	{
		int index = 0;
		ListNode *virt_head = new ListNode;
		virt_head->next = head;
		ListNode *p = virt_head, *q;

		while (p != nullptr) {
			if (index + 1 == left) {
				break;
			}
			index++;
			p = p->next;
		}
		q = p;
		while (q != nullptr) {
			if (index == right) {
				break;
			}
			index++;
			q = q->next;
		}
		ListNode *tmp;
		while (p->next != q) {
			tmp = p->next;
			p->next = tmp->next;
			tmp->next = q->next;
			q->next = tmp;
		}
		head = virt_head->next;
		delete virt_head;
		return head;
	}
};