def partition1(self, head, x): #55ms, 45%
     """
     :type head: ListNode
     :type x: int
     :rtype: ListNode
     """
     if not head:
         return None
     dummy = ListNode(-1)
     dummy.next = head
     left = ListNode(-1)
     ltail = left
     right = ListNode(-1)
     rtail = right
     tmp = head
     while tmp:
         if tmp.val<x:
             ltail.next = tmp
             ltail = ltail.next
         else:
             rtail.next = tmp
             rtail = rtail.next
         tmp = tmp.next
     if left.next:  # need to check if left part is None, otherwise wrong for case2
         dummy.next = left.next
         ltail.next = right.next
     else:
         dummy.next = right.next
     rtail.next = None
     return dummy.next

    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head

        cur = head
        L = 1
        while cur.next is not None:
            cur = cur.next
            L += 1

        cur.next = head  # previous is NULL

        size = L - k % L
        dummy = ListNode(-1)
        dummy.next = head

        for i in range(size):
            dummy = dummy.next

        ret = dummy.next
        dummy.next = None
        return ret

 def test_case2(self):
     head = ListNode(0)
     head.next = None
     n = 1
     answer = None
     result = self.sol.removeNthFromEnd(head, n)
     self.assertEqual(answer, result)

 def deleteDuplicates(self, head): #58ms, 65%
     """
     :type head: ListNode
     :rtype: ListNode
     """
     if not head:
         return None
     dummy = ListNode(0)
     dummy.next = head
     good = dummy
     first = head
     faster = head.next
     while first:
         if faster is None or first.val != faster.val:
             good.next = first
             good = good.next
             first = faster
             if faster:
                 faster = faster.next
         else:
             while faster and faster.val == first.val:
                 faster = faster.next
             first = faster
             faster = first.next if first else None
     good.next = None # need to add ending to good, otherwise wrong for case 2
     return dummy.next

    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head

        dummy = ListNode(-1)
        dummy.next = head
        ###############################################################
        # like remove duplicate from array, pre is the last valid one #
        # and pre.next == cur means the left-side OK one              #
        ###############################################################
        pre = dummy
        cur = head

        while cur.next is not None:
            if cur.val != cur.next.val:  # right-side ok
                if pre.next == cur:      # if left-side ok, add one to result
                    pre = pre.next
                else:
                    pre.next = cur.next  # left-side not ok, new start
            cur = cur.next

        if pre.next == cur:     # cur is the last one, add it to result
            pre = pre.next
        pre.next = None
        return dummy.next

    def swapPairs(self, head): #45ms, 83%
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        dummy = ListNode(0)
        dummy.next = head
        zero = dummy
        one = head
        two = head.next
        while one and two:
            three = two.next
            # one.val, two.val = two.val, one.val   # 32ms, 98%, if use the swap value way
            # zero = two
            # one = three
            # two = one.next if one else None
            zero.next = two
            one.next = three
            two.next = one
            zero = one
            one = one.next
            two = one.next if one else None

        return dummy.next

 def test_case1(self):
     nums = [1,2,3,4,5]
     m =2
     n = 4
     answer = [1,4,3,2,5]
     result = self.sol.reverseBetween(ListNode.parseArray2List(nums),m, n)
     self.assertEqual(answer, ListNode.parseList2Array(result))

 def reverseKGroup(self, head, k): # 85ms, 37%, pay attention to link details, trial and error process
     """
     :type head: ListNode
     :type k: int
     :rtype: ListNode
     """
     if not head:
         return None
     if k==1:
         return head
     dummy = ListNode(-1)
     dummy.next = head
     p = dummy
     done_tail = dummy
     cnt = 0
     while True:
         while cnt < k:
             p = p.next
             if p:
                 cnt+=1
             else:
                 break
         if cnt < k or not p:
             return dummy.next
         next_head = p.next
         new_done = done_tail.next
         done_tail.next = self.reverse_link(done_tail.next,next_head)
         done_tail = new_done
         p = next_head
         if not p:
             return dummy.next
         cnt = 1
     return dummy.next

 def test_case4(self):
     head = ListNode(0)
     n1 = ListNode(1)
     head.next = n1
     n = 1
     answer = head
     result = self.sol.removeNthFromEnd(head, n)
     self.assertEqual(None, result.next)

 def removeNthFromEnd2(self, head, n): # slower 72ms
     dummy=ListNode(0); dummy.next=head
     p1=p2=dummy
     for i in range(n): p1=p1.next
     while p1.next:
         p1=p1.next; p2=p2.next
     p2.next=p2.next.next
     return dummy.next

 def test_case3(self):
     head = ListNode(0)
     n1 = ListNode(1)
     head.next = n1
     n = 2
     answer = n1
     result = self.sol.removeNthFromEnd(head, n)
     self.assertEqual(answer, result)

 def reverse_link(self, head, tail):
     dummy = ListNode(-1)
     dummy.next = head
     p = head.next
     while p!=tail:
         new_next = p.next
         head.next = new_next
         p.next = dummy.next
         dummy.next = p
         p = new_next
     return dummy.next

 def reverseBetween_ref(self, head, m, n):
     if head == None or head.next == None:
         return head
     dummy = ListNode(0); dummy.next = head
     head1 = dummy
     for i in range(m - 1):
         head1 = head1.next
     p = head1.next
     for i in range(n - m):
         tmp = head1.next
         head1.next = p.next
         p.next = p.next.next
         head1.next.next = tmp
     return dummy.next

 def deleteDuplicates_ref(self, head): #69ms, 35%
     if head == None or head.next == None:
         return head
     dummy = ListNode(0); dummy.next = head
     p = dummy
     tmp = dummy.next
     while p.next:
         while tmp.next and tmp.next.val == p.next.val:
             tmp = tmp.next
         if tmp == p.next:
             p = p.next
             tmp = p.next
         else:
             p.next = tmp.next
     return dummy.next

    def reverseList_itera(self, head): # iterative way , 49ms, 67%
        """
        remember to do it in on pass!!!
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return head
        dummy = ListNode(0)

        while head:
            tmp = head
            head = head.next
            tmp.next = dummy.next
            dummy.next = tmp
        return dummy.next

 def test_case04(self):
     nums = [0,1,2]
     k = 3
     from util.list_node import ListNode
     head = ListNode.parseArray2List(nums)
     #answer = [head, head.next, head.next.next, head.next.next.next, None]
     result = self.sol.splitListToParts(head, k)
     pass

 def splitListToParts(self, root, k):
     """
     :type root: ListNode
     :type k: int
     :rtype: List[ListNode]
     """
     if not root:
         return [ [] for _ in range(k)]
     list_len = self.find_len(root)
     short_len = list_len / k
     long_cnt = list_len % k
     #long_len = short_len + list_len % k
     long_len = short_len + 1
     dummy = ListNode(-1)
     dummy.next = root
     res = []
     curr = dummy
     tmp = dummy.next
     for i in range(long_cnt):
         res.append(tmp)
         curr = tmp
         for j in range(long_len-1):
             curr = curr.next
         tmp = curr.next
         curr.next = None
     # tmp = curr.next if curr else None
     dummy = ListNode(-1)
     dummy.next = tmp
     curr = dummy
     for i in range(k - long_cnt):
         if not short_len:
             res.append(None)
             continue
         res.append(tmp)
         curr = tmp
         for j in range(short_len-1):
             if not curr:
                 return res
             curr = curr.next
         if curr:
             tmp = curr.next
             curr.next = None
         else:
             tmp = None
     return res

    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head

        dummy = ListNode(-1)
        dummy.next = head
        tmp = head
        for i in range(2):
            cur = head
            head = head.next
            cur.next = dummy.next
            dummy.next = cur
        tmp.next = self.swapPairs(head)
        return dummy.next

    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head

        fast = dummy
        slow = dummy
        for i in range(n):
            fast = fast.next
        while fast.next is not None:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

    def mergeKListsMinQueue(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        pq = []
        for i in lists:
            if i is not None:
                heapq.heappush(pq, (i.val, i))
        dummy = ListNode(-1)
        tmp = dummy
        while len(pq) > 0:
            val, cur = heapq.heappop(pq)
            dummy.next = cur
            dummy = dummy.next
            if cur.next is not None:
                heapq.heappush(pq, (cur.next.val, cur.next))

        return tmp.next