92. Reverse Linked List II

Problem

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

Solution

/**
 * 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) {
  var newHead = new ListNode(0);
  var now = newHead;
  var tmp = null;
  var reverseLast = null;
  var reverseHead = null;
  var reverseNow = null;
  var i = 0;

  newHead.next = head;

  while (now) {
    tmp = now.next;

    if (i === m - 1) {
      reverseHead = now;
    }

    if (i === m) {
      reverseLast = now;
      reverseNow = now;
    }

    if (i > m && i <= n) {
      now.next = reverseNow;
      reverseNow = now;
    }

    if (i === n) {
      reverseLast.next = tmp;
      reverseHead.next = reverseNow;
    }

    now = tmp;
    i++;
  }

  return newHead.next;
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(1).