反转链表 II

[louzhedong]

习题

出处：LeetCode 算法第92题

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

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

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

思路

顺序遍历，设置临时链表存储中间反转的链表，并标记开始和结束反转的两个节点，最后将链表串联起来

解答

function ListNode(val) {
  this.val = val;
  this.next = null;
}

var reverseBetween = function (head, m, n) {
  var start = new ListNode();
  start.next = head;
  var result = start;
  var count = 1;
  while (count < m) {
    count++;
    start = start.next;
  }
  var flag = start;
  start = start.next;
  var flag2 = start;
  var cursor = new ListNode();
  while (count <= n) {
    var temp = new ListNode(start.val);
    var temp1 = temp;
    if (cursor.val != undefined) {
      temp.next = cursor;
    } else {
      flag2 = temp;
    }
    cursor = temp1;
    start = start.next;
    count++;
  }

  flag2.next = start;
  flag.next = cursor;
  return result.next;
};

var head = new ListNode(1);
var aaa = head;
head.next = new ListNode(-2);
head = head.next;
head.next = new ListNode(-5);
head = head.next;
head.next = new ListNode(0);
head = head.next;
head.next = new ListNode(-4);

console.log(reverseBetween(aaa, 2, 5));