• 题目
• 大致意思
• 解决方案
• 源代码

题目

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

For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

大致意思

给定一个链表，在链表的指定位置中，把部分内容进行反转

解决方案

• 如果链表不存在、或者 m === n，可以直接return head

if (!head || m === n ) return head;

• 找到m、n的位置，并且找到m的前一个node，以及n的下一个node。

var node = head;
var index = 1;
var obj;
var pre, next, h, t;

while (node) {
  if (index === m) {
    h = node; // 头的位置
  }

  if (index === n) {
    t = node; // 尾的位置
    next = node.next; // 后一个

    obj = reverse(h, t); // 找到头尾，进行反转
    break;
  }

  if (!h) pre = node; // 前一个位置
  node = node.next;
  index++;
}

• 将指定位置的内容进行反转

function reverse(head, tail) {
  var list = {};
  tail.next = null;
  var node = head;
  var pre, next;
  var h, t;

  while (node) {
    if (!pre) { // 如果是一个的时候，是没有preNode，所以我们讲这个node的next赋值为next
      pre = node;
      node = node.next;
      pre.next = null;
      t = pre; // 得到这个链表的尾部，方便后续插入
      continue;
    }

    // 将现在的node指向存起来的pre
    next = node.next;
    node.next = pre;
    pre = node;
    node = next;
  }
  return { // 返回整个链表，以及尾部
    node: pre,
    tail: t
  };
}

• 根据前后内容，进行拼接

if (!pre) {
  head = obj.node;
} else {
  pre.next = obj.node;
}
obj.tail.next = next;

return head;

源代码

var reverseBetween = function(head, m, n) {
  if (!head || m === n ) return head;

  var node = head;
  var index = 1;
  var obj;
  var pre, next, h, t;

  while (node) {
    if (index === m) {
      h = node;
    }

    if (index === n) {
      t = node;
      next = node.next;

      obj = reverse(h, t);
      break;
    }

    if (!h) pre = node;
    node = node.next;
    index++;
  }

  if (!pre) {
    head = obj.node;
  } else {
    pre.next = obj.node;
  }
  obj.tail.next = next;

  return head;
};

function reverse(head, tail) {
  var list = {};
  tail.next = null;
  var node = head;
  var pre, next;
  var h, t;
  var flag = true;

  while (node) {
    if (!pre) {
      pre = node;
      node = node.next;
      pre.next = null;
      t = pre;
      continue;
    }

    next = node.next;
    node.next = pre;
    pre = node;
    node = next;
  }
  return {
    node: pre,
    tail: t
  };
}