P195 链表加一

描述#

这个题目说的是，给你一个不为空的单链表，它表示一个非负整数。链表中的每个节点值都位于 0~9 之间，代表整个非负整数中的一位。你要将这个非负整数加 1，然后返回结果链表。

比如说，给你的链表是：
1 -> 2 -> 4
它表示整数 124，加 1 等于 125，于是你要返回链表：
1 -> 2 -> 5

相关视频：数组加一

代码#

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(1)
  public ListNode plusOne(ListNode head) {
    ListNode maybe = new ListNode(0), notNine = maybe;
    maybe.next = head;
    for (ListNode p = head; p != null; p = p.next)
      if (p.val != 9)
        notNine = p;
    notNine.val += 1;
    for (ListNode p = notNine.next; p != null; p = p.next)
      p.val = 0;
    if (notNine == maybe) return maybe;
    else return head;
  }

}