725.分隔链表

链接：725.分隔链表
难度：Medium
标签：链表
简介：给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

题解 1 - javascript

• 编辑时间：2021-09-22
• 执行用时：88ms
• 内存消耗：40.6MB
• 编程语言：javascript
• 解法介绍：储存到队列中进行筛选。

function splitListToParts(head: ListNode | null, k: number): Array<ListNode | null> {
  const list: ListNode[] = [];
  let p: ListNode | null = head;
  while (p) {
    const next = p.next;
    list.push(p);
    p.next = null;
    p = next;
  }
  const len = list.length;
  const ans: Array<ListNode | null> = new Array(k).fill(null);
  if (len <= k) {
    for (let i = 0; i < len; i++) ans[i] = list[i];
    return ans;
  }
  const cnt = ~~(len / k);
  const last = (len % k) - 1;
  let nodeIdx = 0;
  for (let i = 0; i < k; i++) {
    const node = (ans[i] = list[nodeIdx]);
    const lastIdx = nodeIdx + cnt + (i <= last ? 1 : 0);
    let p = node;
    while (++nodeIdx < lastIdx) p = p.next = list[nodeIdx];
  }
  return ans;
}

题解 2 - javascript

• 编辑时间：2021-09-22
• 执行用时：76ms
• 内存消耗：40.2MB
• 编程语言：javascript
• 解法介绍：循环两次。

function splitListToParts(head: ListNode | null, k: number): Array<ListNode | null> {
  let len = 0;
  let p = head;
  for (; p; p = p.next) len++;
  const cnt = ~~(len / k);
  const last = (len % k) - 1;
  const ans: Array<ListNode | null> = [];
  p = head;
  let max = cnt + (ans.length <= last ? 1 : 0);
  let idx = 0;
  while (p) {
    if (idx === 0) ans.push(p);
    if (idx === max - 1) {
      max = cnt + (ans.length <= last ? 1 : 0);
      const next = p.next;
      p.next = null;
      p = next;
      idx = 0;
    } else {
      p = p.next;
      idx++;
    }
  }
  while (ans.length < k) ans.push(null);
  return ans;
}