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
