Sep.14-20 从双倍数组中还原原数组（中等）& 分隔链表（中等）

2007. 从双倍数组中还原原数组

排序+哈希表计数

# python3
class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        l = len(changed)
        if l % 2 == 1:
            return []
        dic = dict()
        res = list()
        changed.sort()
        for i in changed:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        for j in changed:
            if dic[j] > 0:
                if dic[j] > dic.get(j * 2, 0):
                    return []
                else:
                    dic[j] -= 1
                    dic[j * 2] -= 1
                    res.append(j)
        return res

725. 分隔链表

• 先把链表长度遍历一下计算出来。
• 基于这个长度去计算要分成几段，每段多长，取余多出来的部分分给前面，前面的片段各多拿 1 个。
• 链表遍历，按照每段的长度进行剪裁。将每段要剪裁的链表先加入res数组，然后再往后遍历链表，数到该剪掉的地方，再通过 last.next = None 把尾部去掉。

# python3
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, head: ListNode, k: int) -> List[ListNode]:
        cur = head
        n = 0
        while cur:
            cur = cur.next
            n += 1
        fold = n // k
        over_num = n % k
        res = [None] * k
        cur = head
        index = 0
        while cur:
            res[index] = cur
            last = None
            num = fold + 1 if index < over_num else fold
            for _ in range(num):
                last = cur
                cur = cur.next
            last.next = None
            index += 1
        return res