1-5题

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]