Friday, January 13, 2017

Leetcode/G家 -- 369. Plus One Linked List(two pointer)

369. Plus One Linked List(two pointer)
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;
    }
}

2 comments: