import heapq


class Solution:
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        counter = {}
        for num in nums:
            if not counter.get(num):
                counter[num] = 1
            else:
                counter[num] += 1
        
        reverse_dic = {}
        for (key, value) in counter.items():
            neg_value = -value
            if not reverse_dic.get(neg_value):
                reverse_dic[neg_value] = [key]
            else:
                reverse_dic[neg_value].append(key)
        
        heap = list( reverse_dic.keys() )
        heapq.heapify(heap)
        ret = []
        while k > 0:
            value = heapq.heappop(heap)
            key_list = reverse_dic[value]
            k -= len(key_list)
            for key in key_list:
                ret.append(key)
                
        return ret

class Solution:
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if nums is None or len(nums) == 0 or len(nums) == 1:
            return []
        
        multi = 1
        left = [1 for i in range(len(nums))]
        for i in range(1, len(nums)):
            multi *= nums[i - 1] 
            left[i] = multi
        
        multi = 1
        right = [1 for i in range(len(nums))]
        for j in range(len(nums) - 2, -1, -1):
            multi *= nums[j + 1]
            right[j] = multi
        
        ret = []
        for k in range(len(nums)):
            ret.append(left[k] * right[k])
            
        return ret

class Solution:
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ##Divide into two cases
        if nums is None or len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        
        value1 = self.rob_range(nums, 0, len(nums) - 2)
        value2 = self.rob_range(nums, 1, len(nums) - 1)
        
        return max(value1, value2)
        
    def rob_range(self, nums, start, end):
        if end - start == 0:
            return nums[start]
        
        dp = [0 for i in range(len(nums))]
        dp[start] = nums[start]
        dp[start + 1] = max(nums[start + 1], dp[start])
        for i in range(start + 2, end + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i] )
        
        return dp[end]

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ret = 0 
        count = 0
        for item in nums:
            count += ( (item >> 31) & 1 )
        neg = count % 3
    
        for position in range(32):
            count = 0
            for item in nums:
                count += ( (item >> position) & 1 )
            ret += (2 ** position) * ( (count % 3 + neg) % 2 )
        
        if neg:
            return -( ret + 1 )
        
        return ret

class Solution:
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n == 0:
            return [0]
        array = self.grayCode(n - 1)
        symetric = []
        for i in range(len(array)):
            symetric.append(array[i])
        for j in range(len(array)):
            symetric.append(array[len(array) - j - 1] + (1 << (n - 1)) )
        
        return symetric

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
def insert(self, intervals, newInterval):
    """
    :type intervals: List[Interval]
    :type newInterval: Interval
    :rtype: List[Interval]
    """
    if len(intervals) == 0:
    return [newInterval]

    insert_start_index = len(intervals)
    for i in range(0, len(intervals)):
    if newInterval.start <= intervals[i].start:
    insert_start_index = i
    break

    insert_end_index = insert_start_index
    while insert_end_index < len(intervals) and newInterval.end >= intervals[insert_end_index].start:
    insert_end_index += 1

    newInterval.end = max(newInterval.end, 0 if insert_end_index < 1 else intervals[insert_end_index - 1].end)

    ##Do not need insertion
    if insert_start_index >= 1 and newInterval.start <= intervals[insert_start_index - 1].end:
    intervals[insert_start_index - 1].end = max(intervals[insert_start_index - 1].end, newInterval.end)
    return intervals[0:insert_start_index] + intervals[insert_end_index:len(intervals)]
    ##Need insert seperately
    else:
    return intervals[0:insert_start_index] + [newInterval] + intervals[insert_end_index:len(intervals)]

class Solution:
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        lens1 = len(num1)
        lens2 = len(num2)
        if lens1 == 0 or lens2 == 0 or int(num1) == 0 or int(num2) == 0:
            return "0"
        
        ret = ""
        multi_matrix = []
        max_len = -1
        for i in range(0, lens2):
            string = self.multiply_one_digit(num1, num2[-1-i]) + "0" * i
            max_len = max(max_len, len(string))
            multi_matrix.append(string)
            
        has_value = True
        append = 0
        for digit in range(0, max_len):
            has_value = False
            value = 0
            for index in range(len(multi_matrix)):
                if digit < len(multi_matrix[index]):
                    value += int(multi_matrix[index][-1-digit])
            value += append
            append = value // 10
            ret = str(value % 10) + ret
            
        if append != 0:
            ret = str(append) + ret
        return ret
            
            
        
    def multiply_one_digit(self, num, digit):
        ret = ""
        append = 0
        for i in range(0, len(num)):
            result_digit = str((int(num[-1-i])*int(digit) + append) % 10)
            ret = result_digit + ret
            append = (int(num[-1-i])*int(digit) + append) // 10
            
        print (ret)
        print (append)
        if append != 0:
            ret = str(append) + ret
         
        return ret

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        if (head == null || head.next == null) return head;
        ListNode first = head;
        ListNode second = head.next;
        pre.next = first;
        head = second;
        while (true) {
            pre.next = second;
            pre = first;
            ListNode temp = second.next;
            second.next = first;
            if (temp == null) {
                first.next = null;
                return head;
            }
            first = temp;
            second = first.next != null ? first.next : first; #Pay attention to the singular case
        }
    }
}