首页 > 代码库 > LeetCode Plus One Linked List
LeetCode Plus One Linked List
原题链接在这里：https://leetcode.com/problems/plus-one-linked-list/
题目：
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 Linked List. 从头开始做比较方便. 加完再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<ListNode> stk = new Stack<ListNode>();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 Stack<ListNode> stk = new Stack<ListNode>();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 }
LeetCode Plus One Linked List