Medium
https://leetcode.com/problems/plus-one-linked-list/
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:
Input: 1->2->3 Output: 1->2->4思路:Use two pointer, j to travel the linkedlist, i to track the last non 9 digit position.
Add 1 to i, and set the rest digits 0.
Complexity:time O(N), space O(1)
public class Solution { public ListNode plusOne(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode i = dummy; ListNode j = dummy; while(j.next!=null){ j = j.next; if(j.val != 9) i = j; } i.val++;//i is last non 9 digit, add 1 to it and set rest be 0 while(i.next!=null){ i = i.next; i.val = 0; } return dummy.val!=0?dummy:head; } }
这个代码在输入全9的时候会core,因为i是dummy
ReplyDelete乌龙了
Delete