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
给一个节点为非负数的链表&＃xff0c;链表头是高位&＃xff0c;进行加1运算。
解法: 由于链表无法通过坐标来直接访问元素&＃xff0c;从链尾开始操作就很麻烦。如果链尾是高位&＃xff0c;进行加1运算就方便了&＃xff0c;所以先把链表翻转一下&＃xff0c;进行加1运算后&＃xff0c;再把链表翻转回来即可。
Java:
public ListNode plusOne(ListNode head) {ListNode h2 &＃61; reverse(head);ListNode p&＃61;h2;while(p!&＃61;null){if(p.val&＃43;1<&＃61;9){p.val&＃61;p.val&＃43;1;break;}else{p.val&＃61;0;if(p.next&＃61;&＃61;null){p.next &＃61; new ListNode(1);break;}p&＃61;p.next;}}return reverse(h2);
}public ListNode reverse(ListNode head){if(head&＃61;&＃61;null||head.next&＃61;&＃61;null)return head;ListNode p1&＃61;head;ListNode p2&＃61;p1.next;while(p2!&＃61;null){ListNode t &＃61; p2.next;p2.next&＃61;p1;p1&＃61;p2;p2&＃61;t;}head.next&＃61;null;return p1;
}
Python:
# Time: O(n)
# Space: O(1)# Definition for singly-linked list.
class ListNode(object):def __init__(self, x):self.val &＃61; xself.next &＃61; None# Two pointers solution.
class Solution(object):def plusOne(self, head):""":type head: ListNode:rtype: ListNode"""if not head:return Nonedummy &＃61; ListNode(0)dummy.next &＃61; headleft, right &＃61; dummy, headwhile right.next:if right.val !&＃61; 9:left &＃61; rightright &＃61; right.nextif right.val !&＃61; 9:right.val &＃43;&＃61; 1else:left.val &＃43;&＃61; 1right &＃61; left.nextwhile right:right.val &＃61; 0right &＃61; right.nextreturn dummy if dummy.val else dummy.next
Python:
# Time: O(n)
# Space: O(1)
class Solution2(object):def plusOne(self, head):""":type head: ListNode:rtype: ListNode"""def reverseList(head):dummy &＃61; ListNode(0)curr &＃61; headwhile curr:dummy.next, curr.next, curr &＃61; curr, dummy.next, curr.nextreturn dummy.nextrev_head &＃61; reverseList(head)curr, carry &＃61; rev_head, 1while curr and carry:curr.val &＃43;&＃61; carrycarry &＃61; curr.val / 10curr.val %&＃61; 10if carry and curr.next is None:curr.next &＃61; ListNode(0)curr &＃61; curr.nextreturn reverseList(rev_head)
C&＃43;&＃43;:
class Solution {
public:ListNode* plusOne(ListNode* head) {if (!head) return head;ListNode *rev_head &＃61; reverse(head), *cur &＃61; rev_head, *pre &＃61; cur;int carry &＃61; 1;while (cur) {pre &＃61; cur;int t &＃61; cur->val &＃43; carry;cur->val &＃61; t % 10;carry &＃61; t / 10;if (carry &＃61;&＃61; 0) break;cur &＃61; cur->next;}if (carry) pre->next &＃61; new ListNode(1);return reverse(rev_head);}ListNode* reverse(ListNode *head) {if (!head) return head;ListNode *dummy &＃61; new ListNode(-1), *cur &＃61; head;dummy->next &＃61; head;while (cur->next) {ListNode *t &＃61; cur->next;cur->next &＃61; t->next;t->next &＃61; dummy->next;dummy->next &＃61; t;}return dummy->next;}
};
C&＃43;&＃43;: Recursive
class Solution {
public:ListNode* plusOne(ListNode* head) {if (!head) return head;int carry &＃61; helper(head);if (carry &＃61;&＃61; 1) {ListNode *res &＃61; new ListNode(1);res->next &＃61; head;return res;}return head;}int helper(ListNode *node) {if (!node) return 1;int carry &＃61; helper(node->next);int sum &＃61; node->val &＃43; carry;node->val &＃61; sum % 10;return sum / 10;}
};
类似题目&＃xff1a;
[LeetCode] 66. Plus One 加一
All LeetCode Questions List 题目汇总
京公网安备 11010802041100号