56-60题

56、链表中倒数第K节点
因为之前做了好几道双指针的题，所以联想到这道题也能用双指针。
但是不知道为什么不能AC

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if not head:
            return None
        fast, slow = head, head
        for i in range(1, k):
            if not fast:
                return None
            fast = fast.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        return slow

57、合并两个排序链表

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        head = ListNode(-1)
        temp = head
        while l1 and l2:
            if l1.val <= l2.val:
                temp.next = l1
                l1 = l1.next
                temp = temp.next
            else:
                temp.next = l2
                l2 = l2.next
                temp = temp.next
        if l1:
            temp.next = l1
        if l2:
            temp.next = l2
        return head.next

58、翻转链表

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        a, b, c = None, head, head.next
        while c:
            b.next = a
            a, b, c = b, c, c.next
        b.next = a
        return b

59、树的子结构

class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        if pRoot1 == None or pRoot2 == None:
            return False
        return self.isSubtree(pRoot1, pRoot2)

    def isSubtree(self, p1, p2):
        if p2 == None:
            return True
        if p1 == None:
            return p1 == p2
        res = False
        if p1.val == p2.val:
            res = self.isSubtree(p1.left, p2.left) and self.isSubtree(p1.right, p2.right)
        return res or self.isSubtree(p1.left, p2) or self.isSubtree(p1.right, p2)

60、数值的整数次方
看了别人的代码，利用右移一位运算代替除以2
利用位与运算代替了求余运算法%来判断一个数是奇数还是偶数

# -*- coding:utf-8 -*-
class Solution:
    def Power(self, base, exponent):
        # write code here
        if exponent == 0:
            return 1
        if exponent == 1:
            return base
        if exponent == -1:
            return 1/base

        ans = self.Power(base, exponent >> 1)
        ans = ans * ans
        if exponent & 1 == 1:
            ans = ans * base
        return ans