title

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Analyze

1 -> 2 -> 3 -> 4 -> 5
    (4 -> 3 -> 2)

该题是206.ReverseLinked List 的扩展, [m, n] 区间内指针翻转的思路同 206 题, 剩下的就是将 m 的 next 指向 n 指针的 next, 同时将排在 m 前面一位的指针的 next 指向 n。

会存在以下卡题的点:

• 最终返回的值怎么定;
• 如何借助中间变量;

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *   this.val = val;
 *   this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
  const originList = new ListNode(0)
  originList.next = head

  let listNode = originList

  for (let i = 0; i < m - 1; i++) {
    listNode = listNode.next
  }

  let prev = null
  let cur = listNode.next

  for (let i = 0; i < n - m + 1; i++) {
    let next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }

  // 将 m 的 next 指向 n 指针的 next, 同时将排在 m 前面一位的指针的 next 指向 n
  listNode.next.next = cur
  listNode.next = prev
  return originList.next
}

Sister Title

206