92. 反转链表 II

🟠   🔖  链表  🔗 力扣 LeetCode

题目

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4

Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1

Output: [5]

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Follow up: Could you do it in one pass?

题目大意

给定 2 个链表中结点的位置 m, n，反转这个两个位置区间内的所有结点。

解题思路

思路一：迭代法

• 由于有可能整个链表都被反转，所以构造一个新的头结点指向当前的头；
• 找到第一个需要反转的结点的前一个结点 p，从这个结点开始，依次把后面的结点用“头插”法，插入到 p 结点的后面；
• 循环次数用 n-m 来控制。

---

思路二：递归法

使用递归方法来解决这道题的关键在于如何递归地反转链表中的某个子链表，并利用辅助变量 successor 保存反转后的链表连接部分。

• 定义一个辅助函数 reverseN(node, n)，用于反转以 node 为起点的前 n 个节点，并返回反转后的新头节点。
• 当 n === 1 时，说明递归到达了需要反转的最后一个节点，此时保存 node.next 为 successor，以便后续连接反转后的链表片段。
• 通过递归调用 reverseN(node.next, n - 1)，逐步反转前 n 个节点，并将反转后的链表与 successor 相连接。
• 如果 left > 1，则通过递归调用 reverseBetween(head.next, left - 1, right - 1)，逐步遍历到指定的 left 位置。
• 当 left === 1 时，直接返回反转后的头节点。
• 否则，将原链表的 head.next 指向反转后的子链表头节点。

代码

迭代法

/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
	if (!head || left === right) return head;

	let res = new ListNode(0, head);
	let prev = res;

	// 移动prev指针，直至指向left - 1
	for (let i = 0; i < left - 1; i++) {
		prev = prev.next;
	}

	let cur = prev.next;

	// 不断地将 cur.next 插入到 prev.next
	for (let i = 0; i < right - left; i++) {
		let temp = cur.next;
		cur.next = temp.next;
		temp.next = prev.next;
		prev.next = temp;
	}

	return res.next;
};

递归法

var reverseBetween = function (head, left, right) {
	// 记录 right 之后的节点
	let successor = null;

	// 递归反转从 left 开始的 right 个节点
	const reverseN = (node, n) => {
		if (n === 1) {
			// 记录第 n 个节点的下一个节点，即 right+1 的节点
			successor = node.next;
			return node;
		}
		// 递归反转前 n-1 个节点
		const last = reverseN(node.next, n - 1);
		// 调整指针
		node.next.next = node;
		node.next = successor;
		return last;
	};

	// 如果 left === 1，说明从头开始反转
	if (left === 1) {
		return reverseN(head, right);
	}

	// 否则，递归移动到 left 位置，处理区间反转
	head.next = reverseBetween(head.next, left - 1, right - 1);
	return head;
};

相关题目

题号	标题	题解	标签	难度
206	反转链表	[✓]	递归 链表