NC50.链表中的节点每k个一组翻转

题目描述 (opens new window)

题目解析

脑海中应该有个画面，这种翻转链表的题目应该会有个虚拟头结点来处理边界问题。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  //定义一个虚拟头节点
  let dummy = new ListNode(-1);
  //将虚拟头节点的next指针 指向链表的 head 拼接成一个带有虚拟头节点的新的链表
  dummy.next = head;

  // 初始化两个变量，初始值设置和dummy指向同一个变量
  let pre = dummy;
  let end = dummy;

  // 这个判断条件是基于 如果 end.next 为null 说明已经翻转完毕。
  while (end !== null) {
    // 
    for (let i = 0; i < k && end !== null; i++) {
      // end 不等于null 不能保证 end.next 不等于null
      end = end.next;
    }
    // for 循环之后可能end 直接等于null 这个时候此次循环 剩余的节点数已经不满足循环一次了
    // 退出循环
    if (end === null) {
      break;
    }
    let start = pre.next;
    let next = end.next;

    // 断开和后面节点的连接
    end.next = null;
    // 将pre节点连接到翻转之后的链表
    pre.next = reverse(start)
    // 翻转之后start跑到了后面 连接之前的next节点
    start.next = next;
    // 开始新一轮的循环时候
    // pre 放在还未翻转的前一个位置
    pre = start;
    // 将end节点移动到和pre相同的位置
    end = pre;
  }
  return dummy.next;
};
var reverse = function (head) {
  let pre = null;
  let curr = head;
  while (curr !== null) {
    let next = curr.next;
    curr.next = pre;
    pre = curr;
    curr = next;
  }
  return pre
}