PlusOneLinkedList [source code]
public class PlusOneLinkedList {
static
/******************************************************************************/
public class Solution {
public ListNode plusOne(ListNode head) {
boolean carry = false;
ListNode tail = reverse(head);
ListNode curr = tail;
curr.val++;
while (curr != null) {
int sum = curr.val + (carry ? 1 : 0);
if (sum >= 10) {
curr.val = 0;
carry = true;
curr = curr.next;
} else {
curr.val = sum;
carry = false;
break;
}
}
reverse(tail);
if (carry) {
head.val = 1;
ListNode next = head.next;
ListNode newNode = new ListNode(0);
head.next = newNode;
newNode.next = next;
}
return head;
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
/******************************************************************************/
public static void main(String[] args) {
PlusOneLinkedList.Solution tester = new PlusOneLinkedList.Solution();
int[][] inputs = {
{1,2,3}, {1,2,4},
{9}, {1,0},
{8,9,9,9}, {9,0,0,0},
};
for (int i = 0; i < inputs.length / 2; i++) {
ListNode head = ListNode.buildListNode(inputs[2 * i]);
ListNode answer = ListNode.buildListNode(inputs[1 + 2 * i]);
String inputStr = Printer.listNode(head);
String outputStr = Printer.listNode(tester.plusOne(head));
String answerStr = Printer.listNode(answer);
System.out.println(Printer.seperator());
System.out.println(Printer.wrapColor(inputStr, "magenta") + " -> " + outputStr + Printer.wrapColor(", expected: " + answerStr, outputStr.equals(answerStr) ? "green" : "red"));
String headStr = Printer.listNode(head);
System.out.println(Printer.wrapColor("Original input: " + headStr, headStr.equals(outputStr) ? "green" : "red"));
}
}
}
首先先想笨办法, 这个题目的笨办法肯定就是类似保存一个reverse的list, 这样就很好做. 但是我看了一下discussion好像大家都是O(N) time和O(1) space.
要不然说:
- 笨办法
- verbal logic
- topic routine
这样的思考方式有用呢, 我想完上面一句, 好像就有思路了. 这题直接reverse, 然后加下去, 最后reverse过来是不是就行了? 没有说不允许modify, 最后还原就行了;
整个问题大概的思路还是很清晰的, 就是要注意一下不同的变量的更新的时候要稍微小心一些; 最后的速度是1ms (12%), 不是最优解;
discussion的最优解:
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;
}
}
if (j.val != 9) {
j.val++;
} else {
i.val++;
i = i.next;
while (i != null) {
i.val = 0;
i = i.next;
}
}
if (dummy.val == 0) {
return dummy.next;
}
return dummy;
}
}
- i stands for the most significant digit that is going to be incremented if there exists a carry
- dummy node can handle cases such as "9->9>-9" automatically
这个解其实还是挺有意思的, 就是一个具体问题具体分析, 其实不是一个非常依赖iteration或者什么固定思路的解法; 找到increment终止的位置, 从这个位置开始更新就行了; 这个是一个非常适合increment这个particular问题的思路;
另外注意这里dummy head的用法, 这个确实很聪明, 比我这种一旦发现需要进位的时候, 再重新做出来一个node的方法要elegant一些. 当然了, 是一个小的优化, 值得学习. 之前好像有一个问题我自己其实也想到过一次;
所以dummy head这个技术代表的到底是什么样的思想? 什么样的objective能够激发我们想到这个? variable length result? 也许可以是这样. 尤其是如果是LinkedList类问题, 当最后要返回的res不确定长度, 误差范围在1的话, 那么我们就可以直接用dummy head这个技巧了;
另外方法论的角度除外, 这个人代码本身其实写的也挺好的;
这个是一个简化的不错的版本:
public class Solution {
public ListNode plusOne(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode lastNotNine = dummy, node = head;
while (node != null) {
if (node.val != 9) {
lastNotNine = node;
}
node = node.next;
}
lastNotNine.val++;
node = lastNotNine.next;
while (node != null) {
node.val = 0;
node = node.next;
}
return dummy.val == 1 ? dummy : dummy.next;
}
}
这个算法暂时就不看的太深了, 大概知道意思就行了, 以后如果二刷什么的还指望自己可以实现一次, 现在把代码记得太熟也未必就是好事;
At the first glance, I want to reverse the inputs, add one, then reverse back. But that is too intuitive and I don't think this is an expected solution. Then what kind of alg would adding one in reverse way for list?
等于说这题我的这个方法其实是笨办法; +sad
Recursion! With recursion, we can visit list in reverse way! So here is my recursive solution.
这个其实以前是见过的, 就是用recursion的上行过程来完成对LinkedList的reversed traversal, 这个之前有一个题目是绝对见过的一个技巧: use recursion to reversely traverse linked list.
public ListNode plusOne(ListNode head) {
if( DFS(head) == 0){
return head;
}else{
ListNode newHead = new ListNode(1);
newHead.next = head;
return newHead;
}
}
public int DFS(ListNode head){
if(head == null) return 1;
int carry = DFS(head.next);
if(carry == 0) return 0;
int val = head.val + 1;
head.val = val%10;
return val/10;
}
当然, 不是说想到recursion这个问题的算法就立刻自然而然的想到了. 这里这个recursion怎么设计其实也是有学问的, 尤其是返回值是什么;
你要站在一个root的位置, 你这样思考: what information do you wish to obtain from the level under? 自然的一个想法当然就是carry, 他这里也是这么做的; 他这里在最后一个level的处理没有用dummy, 而是用类似我的做法;
这个算法非常的简练, 而且易读, 这个作者的功力还是不错;
但是实际上, 这里返回值的设计并不是绝对的, 这个是stefan的版本, 返回值的设计用的是另外一种思路, 而且他这个版本没有helper:
public ListNode plusOne(ListNode head) {
if (head == null)
return new ListNode(1);
ListNode plused = plusOne(head.next);
if (plused != head.next)
head.val++;
if (head.val <= 9)
return head;
head.val = 0;
plused.next = head;
return plused;
}
Problem Description
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
Difficulty:Medium
Total Accepted:15.4K
Total Submissions:28.3K
Contributor: LeetCode
Companies
google
Related Topics
linked list
Similar Questions
Plus One