Question

Formatted question description: https://leetcode.ca/all/369.html

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

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

Example 1:

Input: head = [1,2,3]
Output: [1,2,4]

Example 2:

Input: head = [0]
Output: [1]

Constraints:

The number of nodes in the linked list is in the range [1, 100].
0 <= Node.val <= 9
The number represented by the linked list does not contain leading zeros except for the zero itself.

Algorithm

Reverse

The head of the table is high digit. Now let’s add 1 operation. The difficulty of this problem is that the linked list cannot access the elements by coordinates, and can only be done by traversal.

Then we think in reverse, if the end of the chain is high, then it is much more convenient to add 1 operation, and you can directly perform calculations while traversing.

So what we can do is to reverse the linked list first, and now the end of the chain is high, we add 1 to the end of the processing operation, and then reverse the linked list back.

First non-9 digit, +1, then set 0 for following

Traverse the linked list and find the first number from the right that is not 9.

If you can’t find such a number, it means that all the numbers are 9, then create a new node with a value of 0 in the header, add 1 to it, and then set all the numbers on the right to 0. for example:

For example, 1->2->3, then the first number that is not 9 is 3. Add 1 to 3 to become 4, and there is no node on the right, so no processing is done, and 1->2-> 4.

For example, 8->9->9, find the first number that is not 9 is 8, and add 1 to become 9, and then set all the following numbers to 0 to get the result 9->0- >0.

For example, in the case of 9->9->9, if a number other than 9 is not found, then create a new node with a value of 0 in the front, add 1 to the process to become 1, and set all the following numbers 0, get 1->0->0->0.

Code

public class Plus_One_Linked_List {

    public ListNode plusOne_9(ListNode head) {

        ListNode cur = head, right = null;

        while (cur != null) {
            if (cur.val != 9) right = cur;
            cur = cur.next;
        }
        if (right == null) {
            right = new ListNode(0);
            right.next = head;
            head = right;
        }
        ++right.val;
        cur = right.next;
        while (right != null) {
            cur.val = 0;
            cur = cur.next;
        }
        return head;
    }


    public ListNode plusOne(ListNode head) {
        ListNode h2 = reverse(head);

        ListNode p = h2;

        while (p != null) {
            if (p.val + 1 <= 9) {
                p.val = p.val + 1;
                break;
            } else {
                p.val = 0;
                if (p.next == null) {
                    p.next = new ListNode(1);
                    break;
                }
                p = p.next;
            }
        }

        return reverse(h2);
    }

    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null)
            return head;

        ListNode p1 = head;
        ListNode p2 = p1.next;
        while (p2 != null) {
            ListNode t = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = t;
        }

        head.next = null;

        return p1;
    }
}

############

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode target = dummy;
        while (head != null) {
            if (head.val != 9) {
                target = head;
            }
            head = head.next;
        }
        ++target.val;
        target = target.next;
        while (target != null) {
            target.val = 0;
            target = target.next;
        }
        return dummy.val == 1 ? dummy : dummy.next;
    }
}

// OJ: https://leetcode.com/problems/plus-one-linked-list/
// Time: O(N)
// Space: O(1)
class Solution {
private:
    ListNode *reverse(ListNode *head) {
        ListNode dummy(0);
        while (head) {
            auto p = head;
            head = head->next;
            p->next = dummy.next;
            dummy.next = p;
        }
        return dummy.next;
    }
public:
    ListNode* plusOne(ListNode* head) {
        head = reverse(head);
        ListNode *p = head;
        int carry = 1;
        while (carry) {
            p->val++;
            carry = p->val / 10;
            p->val %= 10;
            if (!p->next) break;
            p = p->next;
        }
        if (carry) p->next = new ListNode(1);
        return reverse(head);
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def plusOne(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        target = dummy
        while head:
            if head.val != 9:
                target = head
            head = head.next
        target.val += 1
        target = target.next
        while target:
            target.val = 0
            target = target.next
        return dummy if dummy.val else dummy.next

############

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
  def plusOne(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """

    def reverse(cur):
      pre = None
      while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
      return pre

    p = head = reverse(head)
    carry = 1
    pre = None
    while p:
      val = (p.val + carry) % 10
      carry = 1 if val < p.val else 0
      p.val = val
      pre = p
      p = p.next

    if carry == 1:
      pre.next = ListNode(1)
    return reverse(head)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func plusOne(head *ListNode) *ListNode {
	dummy := &ListNode{0, head}
	target := dummy
	for head != nil {
		if head.Val != 9 {
			target = head
		}
		head = head.Next
	}
	target.Val++
	target = target.Next
	for target != nil {
		target.Val = 0
		target = target.Next
	}
	if dummy.Val == 1 {
		return dummy
	}
	return dummy.Next
}

369 - Plus One Linked List

Question

Algorithm

Reverse

First non-9 digit, +1, then set 0 for following

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Reverse

First non-9 digit, +1, then set 0 for following

Code

All Problems

All Solutions