反转链表II（92）

题目

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明

1 ≤ m ≤ n ≤ 链表长度。

示例

输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

算法

递归反转

需要反转链表的[m, n]个节点

我们使用变量reverseBefore来保存反转部分的前一个节点m-1

使用变量reverseNext来保存反转部分的后一个节点n+1

使用变量reverseHead来保存反转部分反转后的头节点n

使用变量reverseEnd来保存反转部分反转后的尾节点m

然后重新连接链表m-1 -> n和m -> n+1

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const reverseBetween = (head, m, n) => {
	if (!head || !head.next) return head;
	let sentinel = new ListNode(0, head);
  let node = sentinel;
  // 找到m-1
	let start = m;
	while (--start > 1) {
		node = node.next;
  }
  // 反转链表
	let reverseBefore = node;
	let reverseEnd = node.next;
	let reverseHead, reverseNext;
	const reverse = (node, k) => {
		if (k === n) {
			reverseNext = node.next;
			return node;
		}
		let reverseHead = reverse(node.next, k + 1);
		node.next.next = node;
		node.next = null;
		return reverseHead;
  };
  // 重新连接链表
	reverseHead = reverse(reverseEnd, m);
	reverseBefore.next = reverseHead;
	reverseEnd.next = reverseNext;
	return sentinel.next;
};

迭代反转

和思想类似：先找到第m个节点，然后迭代的反转节点直到第n个节点，然后重新拼接链表m-1 -> n和m -> n+1

需要说明的是使用迭代的方法反转链表，对于链表A -> B -> C -> D，我们创建三个变量pre、cur、next分别指向节点A、B、C：

// 我们需要改变链表指向为：A <- B -> C -> D
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;

这里我们使用next变量来保存cur的下一个节点，因为在改变链表方向的时候我们会改变cur.next，当我们需要反转一部分链表的时候，我们重复上面的代码即可

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
const reverseBetween = (head, m, n) => {
  if(!head) return head;
	let sentinel = new ListNode(0, head);
	let node = sentinel;
	let start = m;
	while (--start > 0) {
		node = node.next;
	}
	let reverseBefore = node;
	let reverseEnd = node.next;
	let pre = node;
	let cur = node.next;
	let next = null;
	while (m++ <= n) {
		next = cur.next;
		cur.next = pre;
		pre = cur;
		cur = next;
	}
	reverseBefore.next = pre;
	reverseEnd.next = cur;
	return sentinel.next;
};