LeetCode 725. Split Linked List in Parts (分裂链表)
Given a (singly) linked list with head node root
, write a function to split the linked list into k
consecutive linked list "parts".
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.
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.
Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]
Example 1:
Input:
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
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 [].
Example 2:
Input:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
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.
题目标签:Linked List
Java Solution:
Runtime beats 59.09%
完成日期:12/07/2017
关键词:singly-linked list
关键点:计算出base 和 leftover
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution
{
public ListNode[] splitListToParts(ListNode root, int k)
{
ListNode[] list = new ListNode[k];
int len = 0;
ListNode cursor = root;
int base = 0;
int leftover = 0; // count the length
while(cursor != null)
{
cursor = cursor.next;
len++;
} // calculate the base and leftover
base = len / k;
leftover = len % k;
cursor = root; // iterate each group
for(int i=0; i<k; i++)
{
list[i] = cursor; // save this group head
ListNode tail = null;
int groupSize = base; // set up correct group size
if(leftover > 0)
{
groupSize++;
leftover--;
} // iterate this group nodes
for(int j=0; j<groupSize; j++)
{
if(j == groupSize - 1) // approach to the end of this group
tail = cursor; cursor = cursor.next;
} if(groupSize > 0) // link this group tail to null
tail.next = null;
} return list;
}
}
参考资料:N/A
LeetCode 题目列表 - LeetCode Questions List
题目来源:https://leetcode.com/
最新文章
- [css]我要用css画幅画(七) - 哆啦A梦
- UVA - 11584 Partitioning by Palindromes[序列DP]
- paramiko模块-2
- Ubuntu下使用Git和GitHub
- NOIP2012 同余方程-拓展欧几里得
- hdu 1496 Equations
- Hopfield模型
- HTTP服务负载均衡总结
- Spring源代码由浅入深系列五 GetBean
- asm 盘头损失,破坏
- Gym 101667I Slot Machines
- n级阶梯,每次走一步或两步,问最多有多少种走法 二叉树实现
- zip4j实现文件压缩与解压缩 &; common-compress压缩与解压缩
- apache-2.4.6 mod_bw-0.92 实现限速上传或下载
- 记录7: office 2016 Mac不能使用的解决过程
- 一套能体现 RBAC 的表结构设计
- c# 静态构造函数与构造函数的调用先后
- vue-cli项目开发/生产环境代理实现跨域请求+webpack配置开发/生产环境的接口地址
- SDIBT 2345 (3.2.1 Factorials 阶乘)
- 设计模式学习---UML常见关系的实现