-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-369-Plus-One-Linked-List.java
111 lines (92 loc) · 3.08 KB
/
LeetCode-369-Plus-One-Linked-List.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// 1. Reverse List, and plus one and reverse back
// public ListNode plusOne(ListNode head) {
// if (head == null) return head;
// ListNode curr = reverse(head);
// printList(curr);
// ListNode dummy = new ListNode(-1);
// ListNode prev = dummy;
// int carry = 1;
// while(curr != null) {
// prev.next = new ListNode((curr.val + carry) % 10);
// carry = (curr.val + carry) / 10;
// curr = curr.next;
// prev = prev.next;
// }
// if (carry != 0) {
// prev.next = new ListNode(carry);
// }
// return reverse(dummy.next);
// }
// private ListNode reverse(ListNode head) {
// ListNode dummy = new ListNode(-1);
// dummy.next = head;
// ListNode prev = head, curr = head.next;
// while (curr != null) {
// prev.next = curr.next;
// curr.next = dummy.next;
// dummy.next = curr;
// curr = prev.next;
// }
// return dummy.next;
// }
// public void printList(ListNode head) {
// String str = head.val + "";
// head = head.next;
// while (head != null) {
// str += " -> " + head.val;
// head = head.next;
// }
// System.out.println(str);
// }
// 2.Two Pointers
/*
https://leetcode.com/problems/plus-one-linked-list/discuss/84125/Iterative-Two-Pointers-with-dummy-node-Java-O(n)-time-O(1)-space
*/
// public ListNode plusOne(ListNode head) {
// if (head == null) return head;
// ListNode dummy = new ListNode(0);
// dummy.next = head;
// ListNode lastNonNineNode = dummy;
// ListNode lastNode = dummy;
// while (lastNode.next != null) {
// lastNode = lastNode.next;
// if (lastNode.val != 9) lastNonNineNode = lastNode;
// }
// if (lastNode.val != 9) {
// lastNode.val++;
// } else {
// lastNonNineNode.val++;
// while(lastNonNineNode.next != null) {
// lastNonNineNode = lastNonNineNode.next;
// lastNonNineNode.val = 0;
// }
// }
// return dummy.val == 0 ? dummy.next : dummy;
// }
// 3.DFS
/*
https://leetcode.com/problems/plus-one-linked-list/discuss/84130/Java-recursive-solution
*/
public ListNode plusOne(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
helper(dummy);
return dummy.val == 0 ? head : dummy;
}
private int helper(ListNode node){
if(node == null) return 1;
node.val += helper(node.next);
if(node.val <= 9) return 0;
node.val %= 10;
return 1;
}
}