Split Linked List in Parts（LeetCode725）

参加LeetCode weekly contest 58时的一道价值5分的题，是关于数据结构的

要求将一个链表均分为k份，如果不能均分（例如链表有6个节点而k=5），则各个部分差不能大于1，链表中允许为空

解题思路：

     我是先求出链表的长度记为llen，然后llen / k得到每一部分赢至少有几个节点，记为n；然后用llen mod k求出有几个链表需要多加1个节点记为c；剩下的操作就是添加节点了，定义一个指针p用来指向要被添加的元素，一直移动就好了

AC代码

#encoding:utf-8
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def splitListToParts(self, root, k):
        """
        :type root: ListNode
        :type k: int
        :rtype: List[ListNode]
        """
        llen = 0;
        myList = []
        
        #计算root的长度
        p = root
        while p is not None:
            llen = llen+1
            p = p.next
        
        #计算最少的部分有几个元素
        #计算有几部分多出一个元素
        n = llen / k;
        c = llen % k;
        
        p = root #指向要被选择的元素

        #加入列表
        for i in range(0,k):
            head = ListNode(1) #每一部分的头
            if n == 0 and i >= c:
                myList.append(None)
            else:
                q = head
                if i < c:
                    for j in range(0,n+1):
                        q.next = p
                        p = p.next
                        q = q.next
                        q.next = None
                        
                else:
                    for j in range(0,n):
                        q.next = p
                        p = p.next
                        q = q.next
                        q.next = None
                        
                head = head.next
                myList.append(head)
        
        return myList