Plus One Linked List

首先可以反过来链表再加1，这是最直观的做法了，但是代码长，主要链表的题个人都不是很喜欢用递归方式做

class Solution(object):
    def plusOne(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def reverse(head):
            pre, nxt = None, None
            while head:
                nxt = head.next
                head.next = pre
                pre = head
                head = nxt
            return pre

        root = reverse(head)
        cur = root
        step = 1
        while cur:
            step, cur.val = divmod(cur.val + step, 10)
            if not step:
                break
            cur = cur.next

        result = reverse(root)
        if step:
            tmp = ListNode(1)
            tmp.next = result
            return tmp
        return result