美文网首页
Leetcode725

Leetcode725

作者: zhouwaiqiang | 来源:发表于2018-11-14 19:47 被阅读0次

题目

  • 给定一个单链表并给定其头结点root,写一个函数实现将其分割为k个连续的链表
  • 每一部分链表的长度要求:两个链表部分的长度不能超过1,某些链表可以置位空(null)
  • 这些部分链表必须要按照输入链表的顺序,并且前一部分的长度必须大于等于后面部分的链表长度
  • 返回一个分段链表头节点组成的数组
  • 举例来说给定输入1->2->3->4, k = 5 返回[[1],[2],[3],[4],null]
  • 给定root = [1, 2, 3], k = 5,返回[[1],[2],[3],[],[]]
  • 给定root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3,返回Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]

解题思路

  • 首先,给定一个k,一个链表,假设链表长度为length,也即是我们要将链表分为k部分,且每两部分的长度不能超过1,那么按照正常的思想我们就是均分呗,那样就都是一样的
  • 但是现在问题来了,我们均分之后即是length/k不能整除,也即是存在余数,此时余数remain=length % k, 既然不能超过1那么我们能做的只有取数组的前remain个数,分别将它的节点数再加1就可以完成我们的目标,有点类似于我们有10个硬币放进三个罐子,任意两个罐子之间的差值不能大于1,按照均分每个罐子3个硬币,此时还剩了一个硬币,再按照从头开始排放入第一个罐子形成4,3,3。如果是11个硬币就是形成4,4,3以此类推
  • 在我们确定了平均值和average和remain之后就可以开始给数组装填数据了,数组中每个数对应的链表长度都应该是average或者average+1,形成一个数组的遍历
  • 在数组遍历内部每次根据所需分段链表长度然后对链表进行遍历,将分段尾节点的next修改为null,head存入数组即可完成内循环,然后整体就完成了。

源代码实现

/**
 * 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[] result = new ListNode[k];
        int count = 0;
        ListNode index = root;
        while (index != null) {
            count++;
            index = index.next;
        }
        int average = count/k;//平均的
        int remaining = count % k;//剩余的
        index = root;
        ListNode head = root;//每一段的头
        for (int i = 0; i < k; i++) {
            int total = i < remaining ? average + 1 : average;
            for (int j = 0; j < total - 1; j++) {   
                if (index != null) index = index.next;
            }
            result[i] = head;
            ListNode last = index;
            if (last != null) {
                index = index.next;
                head = index;
                last.next = null;
            } else head = null;
        }
        return result;
    }
}

相关文章

  • Leetcode725

    题目 给定一个单链表并给定其头结点root,写一个函数实现将其分割为k个连续的链表 每一部分链表的长度要求:两个链...

网友评论

      本文标题:Leetcode725

      本文链接:https://www.haomeiwen.com/subject/yncsfqtx.html