Interview Classic 150 Problem 92: Reverse Linked List II

---

Timeline

Timeline

2025-11-20

init

Linked List

---

Problem:

P92 Reverse Linked List II

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

In linked list problems, you generally cannot directly change the value of nodes.

Using the head insertion method to reverse a linked list, creating a dummy head node can avoid some special cases. Also, at the end, you should not return head, but virt_head->next, because head may change due to swapping.

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;
	}
};