原题&翻译

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.
给一个单链表的第一个节点 root,写一个分割函数,将其链表分割为连续的 K 部分。

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.
每一个部分长度尽可能相同:每个部分长度相差最大为 1。有些部分可能为空。

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.
每个部分的数据必须按照以前的顺序排列,且只能前面的部分长度大于后面的部分。

Return a List of ListNode’s representing the linked list parts that are formed.
返回 ListNode 组成的链表向量。

比如 1->2->3->4, k = 5 // 5 个等长部分 [ [1], [2], [3], [4], null ]

例子 1:

Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it’s string representation as a ListNode is [].

例子 2:

Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Note:

  • The length of root will be in the range [0, 1000].
  • Each value of a node in the input will be an integer in the range [0, 999].
  • k will be an integer in the range [1, 50].

解析

一般解法

  1. 本题基本两个问题,第一怎么分段,第二就是指针基本功了。
  2. 首先,先保证平均整除分配,没有多余最好,有多余的部分,从头开始,一人多分一个,先到先得,这样,分配就完成了。
  3. 然后分割链表,我的做法是,先把整个都分配进去,然后按照本身长度分割掉剩余部分,然后将剩余的给下一个部分,再次按照长度切割,剩余部分继续分配。有点浪费空间。

快一点的方法

目前看到最快的是 6ms ,其实方法都大同小异。

Hello world!
文章已创建 200

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部