原题链接在这里：

题目：

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

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

Example:

Input:1->2->3Output:1->2->4

题解：

Method 1:

末位加一，若是有进位，就要在 Linked List 的前一个 Node 做改动，自然而然想到先. 从头开始做比较方便. 加完再reverse回来.

Time Complexity: O(n). reverse 用O(n), reverse 两次 加上 iterate 一次.

Space: O(1).

AC Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     public ListNode plusOne(ListNode head) {11         if(head == null){12             return head;13         }14         ListNode tail = reverse(head);15         ListNode cur = tail;16         ListNode pre = cur;17         int carry = 1;18         19         while(cur != null){20             pre = cur;21             int sum = cur.val + carry;22             cur.val = sum%10;23             carry = sum/10;24             if(carry == 0){25                 break;26             }27             cur = cur.next;28         }29         if(carry == 1){30             pre.next = new ListNode(1);31         }32         return reverse(tail);33     }34     35     private ListNode reverse(ListNode head){36         if(head == null || head.next == null){37             return head;38         }39         ListNode tail = head;40         ListNode cur = head;41         ListNode pre;42         ListNode temp;43         44         while(tail.next != null){45             pre = cur;46             cur = tail.next;47             temp = cur.next;48             cur.next = pre;49             tail.next = temp;50         }51         return cur;52     }53 }

Method 2:

利用递归，因为递归的终止条件就是到了末尾节点，每层向上返回一个carry数值.

Time Complexity: O(n), 最多每个节点iterate两遍.

Space: O(n), recursion用了n层stack.

AC Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     public ListNode plusOne(ListNode head) {11         if(head == null){12             return head;13         }14         int carry = dfs(head);15         if(carry == 1){16             ListNode dummy = new ListNode(1);17             dummy.next = head;18             return dummy;19         }20         return head;21     }22     23     private int dfs(ListNode head){24         if(head == null){25             return 1;26         }27         int carry = dfs(head.next);28         int sum = head.val + carry;29         head.val = sum%10;30         return sum/10;31     }32 }

Method 3:

和Method 2原题相同，用stack代替recursion.

Time Complexity: O(n).

Space: O(n). Stack 大小.

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     public ListNode plusOne(ListNode head) {11         if(head == null){12             return head;13         }14         Stack
     
       stk = new Stack
      
       ();15         ListNode cur = head;16         while(cur != null){17             stk.push(cur);18             cur = cur.next;19         }20         int carry = 1;21         while(!stk.isEmpty() && carry == 1){22             ListNode top = stk.pop();23             int sum = top.val + carry;24             top.val = sum%10;25             carry = sum/10;26         }27         if(carry == 1){28             ListNode dummy = new ListNode(1);29             dummy.next = head;30             return dummy;31         }32         return head;33     }34 }
      
     

Method 4:

从右向左寻找第一个不是9的节点，找到后在该节点加一,  若是他后面还有节点, 说明后面的节点都是9, 所以都要变成0.

Time Complexity: O(n).

Space: O(1).

AC Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 public class Solution {10     public ListNode plusOne(ListNode head) {11         if(head == null){12             return head;13         }14         15         ListNode dummy = new ListNode(0);16         dummy.next = head;17         ListNode cur = dummy;18         ListNode notNine = dummy;;19         while(cur != null){20             if(cur.val != 9){21                 notNine = cur;22             }23             cur = cur.next;24         }25         26         notNine.val += 1;27         cur = notNine.next;28         while(cur != null){29             cur.val = 0;30             cur = cur.next;31         }32         return notNine == dummy ? dummy : head;33     }34 }