369. 给单链表加一

369. 给单链表加一
用一个 非空 单链表来表示一个非负整数，然后将这个整数加一。

你可以假设这个整数除了 0 本身，没有任何前导的 0。

这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:

输入: [1,2,3]
输出: [1,2,4]

#解析 两种方法，一种最笨的就是翻转2次，第二种就是找到一个不是9的直接加，然后后面的都变为0

//翻转2次
/**
 * 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 pre = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        //这时候头是pre
        pre.val = pre.val+1;
        //head3作为一个标识，用来第二次翻转的头部
        ListNode head3 = pre;

        int jinwei = 0;

        //这里head2代表尾部
        ListNode head2 = null;
        while(pre!=null){
            int sum = pre.val+jinwei;
            pre.val = sum%10;
            jinwei = sum/10;
            head2 = pre;
            pre = pre.next;
        }
        if(jinwei!=0){
            ListNode tmp = new ListNode(jinwei);
            head2.next = tmp;
            head2 = head2.next;
        }

        //这时候对于head2 进行翻转
        pre = null;
        while(head3!=null){
            ListNode next = head3.next;
            head3.next = pre;
            pre = head3;
            head3 = next;
        }
        return pre;



    }
}

//直接加
class Solution {
  public ListNode plusOne(ListNode head) {
    // sentinel head
    ListNode sentinel = new ListNode(0);
    sentinel.next = head;
    ListNode notNine = sentinel;

    // find the rightmost not-nine digit
    while (head != null) {
      if (head.val != 9) notNine = head;
      head = head.next;
    }
    
    // increase this rightmost not-nine digit by 1
    notNine.val++;
    notNine = notNine.next;
    
    // set all the following nines to zeros
    while (notNine != null) {
      notNine.val = 0;
      notNine = notNine.next;
    }
    
    return sentinel.val != 0 ? sentinel : sentinel.next;
  }
}

注意：本文归作者所有，未经作者允许，不得转载