1、二叉树的镜像
二叉树很自然的联想到递归，只需要递归翻转左子树和右子树，然后交换左右子树的位置就行了
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root:
self.invertTree(root.left)
self.invertTree(root.right)
root.left, root.right = root.right, root.left
return root
else:
return root
2、链表中环的入口节点
之前做过判断链表有环的题，只需要设置一个快指针一个慢指针即可判断有无环。但是这题不会做，参考了别人的思路（https://blog.csdn.net/willduan1/article/details/50938210），还是设置两个指针。自己推导了一遍公式后用python实现。
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
fast = head
slow = head
while fast.next:
if not fast.next.next:
return None
else:
fast = fast.next.next
slow = slow.next
if fast == slow:
if fast==head:
return head
slow = head
while True:
fast = fast.next
slow = slow.next
if fast == slow:
return fast
return None
3、删除链表中的重复节点，感觉代码写得很烂，重新构造了一个新链表来存储
class Solution:
# @param head, a ListNode
# @return a ListNode
def deleteDuplicates(self, head):
if not head:
return None
head_temp = ListNode(head.val-1)
head_temp.next = head
rst = ListNode(0)
rst1 = ListNode(0)
rst.next = rst1
cur_node = head
val_temp = head_temp.val
while cur_node:
if cur_node.next:
next_node = cur_node.next
if val_temp != cur_node.val != next_node.val:
rst1.next = cur_node
rst1 = rst1.next
val_temp = cur_node.val
cur_node = cur_node.next
else:
if cur_node.val != val_temp:
rst1.next = cur_node
return rst.next.next
else:
rst1.next = None
return rst.next.next
4、从尾到头打印链表
class Solution:
def printListNode(self, head):
if not head:
return None
else:
rst = []
cur = head
while cur:
rst.append(cur)
cur = cur.next
return rst[::-1]
5、求斐波那契数列的第n项
class Solution:
def fib(self, n):
memory = [1, 1]
if n == 0:
return None
elif n==1:
return 1
else:
for i in range(2, n):
memory.append(memory[i-1]+memory[i-2])
return memory[n-1]
