206.92.25 反转链表.md

206. 反转链表

迭代

var reverseList = function(head) {
  if (!head) return null;
  let dummy = null;
  while(head && head.next) {
    let next = head.next;
    head.next = dummy;
    dummy = head;
    head = next;
  }
  head.next = dummy;
  return head;
};

递归

var reverseList = function(head) {
  if (!head || !head.next) {
    return head;
  }
  let dummy = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return dummy
};

92. 反转链表II

/**
 * 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) {
  if (m == n) return head;
  let count = 1, list = head, prev = null, post = null;
  while(head && count < m) {
    prev = head;
    head = head.next;
    count ++;
  }
  let dummy = null, cur = head;
  while(head && head.next && count < n) {
    let next = head.next;
    head.next = dummy;
    dummy = head;
    head = next;
    post = head.next;
    count ++;
  }
  head.next = dummy;

  if (m !== 1) {
    prev.next = head;
  }
  cur.next = post;

  return m == 1 ? head : list;
};

25. K个一组反转链表

翻转拼接那里搞不懂。。。

var reverseKGroup = function(head, k) {
    if (k === 1) return head;
    let len = 0, list = head;
    // 找出长度
    while(list) {
      len ++;
      list = list.next;
    }
    // 计算可以遍历的长度
    const cycle = ~~(len / k);
    // 需要走的总长度
    let allLen = cycle * k;

    let count = 0, dummy = null, prev, end, realHead
    while(head && head.next && count < allLen) {
      // 保存头结点
      if (isPrev(count, k)) {
        prev = head;
      }
      let next = head.next;
      // 保存尾结点
      if (isEnd(count, k)) {
        end = head;

        // 第一次循环的尾结点用作返回时的真正的头结点
        !realHead && (realHead = head);
      }
      
      // 将下一个头结点挂到上一个尾结点上
      if (prev && end) {
        prev.next = end;
        // 清掉尾结点
        end = null;
      }

      if (isPrev(count, k)) {
        dummy = null;
      } else {
        head.next = dummy;
        dummy = head;
      }

      head = next;

      count ++;
    }
    return realHead
};

function isPrev(count, k) {
  return !(count % k)
}

function isEnd(count, k) {
  return !((count + 1) % k)
}