369.Plus One Linked List

[chengchengxu15]

https://www.lintcode.com/problem/904/description

Description Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Example Example1

Input: 1 -> 2 -> 3 -> null Output: 1 -> 2 -> 4 -> null Explanation: 123 + 1 = 124 Example2

Input: 9 -> 9 -> null Output: 1 -> 0 -> 0 -> null Explanation: 99 + 1 = 100

[chengchengxu15]

Solution 1: 记录两个指针，其中r指的是当前位置，l的含义是当前最后一个不为9的数字 当r遍历到null时，我们只需要让l的next节点到null的所有节点的值全都归零，然后将l对应的值+1即可 时间复杂度O(n),n为链表长度

class Solution:
    """
    @param head: the first Node
    @return: the answer after plus one
    """
    def plusOne(self, head):
        # Write your code here
        new_list = ListNode(0)
        new_list.next = head
        r = new_list
        l = new_list
        while r.next != None:

            r = r.next
            if (r.val != 9):
                l = r
        print(r.val, l.val)

        if r.val != 9:
            r.val += 1
        else:
            l.val += 1
            l = l.next
            while(l != None):
                l.val = 0
                l = l.next

        if new_list.val == 0:
            return new_list.next

        else:
            return new_list

[chengchengxu15]

Solution 2: https://www.lintcode.com/problem/904/solution/33018 先反转list, +1, 如果超过9，进位（list.next）,最后再反转list

class Solution:
    """
    @param head: the first Node
    @return: the answer after plus one
    """

    def plusOne(self, head):
        reversedList = self.Reverse(head) # 翻转
        cur = reversedList
        res = None
        carrying = 1
        # 依次按位加
        while cur and carrying != 0::
            temp = cur.val + carrying;
            cur.val = temp % 10;
            carrying = temp // 10;
            res = cur;
            cur = cur.next;
        # 若最高位有进位则再插入一个节点
        if carrying != 0:
            res.next = ListNode(carrying)
        return self.Reverse(reversedList) #再次翻转

    def Reverse(self,head):
        res = None
        cur = head
        while cur:
            temp = cur.next;
            cur.next = res;
            res = cur;
            cur = temp;
        return res