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->3 Output:
1->2->4
给一个节点为非负数的链表，链表头是高位，进行加1运算。
解法: 由于链表无法通过坐标来直接访问元素，从链尾开始操作就很麻烦。如果链尾是高位，进行加1运算就方便了，所以先把链表翻转一下，进行加1运算后，再把链表翻转回来即可。
Java:
public ListNode plusOne(ListNode head) {
ListNode h2 = reverse(head);
ListNode p=h2;
while(p!=null){
if(p.val+1<=9){
p.val=p.val+1;
break;
}else{
p.val=0;
if(p.next==null){
p.next = new ListNode(1);
break;
}
p=p.next;
}
}
return reverse(h2);
}
public ListNode reverse(ListNode head){
if(head==null||head.next==null)
return head;
ListNode p1=head;
ListNode p2=p1.next;
while(p2!=null){
ListNode t = p2.next;
p2.next=p1;
p1=p2;
p2=t;
}
head.next=null;
return p1;
}
Python:
# Time: O(n)
# Space: O(1) # Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None # Two pointers solution.
class Solution(object):
def plusOne(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None dummy = ListNode(0)
dummy.next = head left, right = dummy, head
while right.next:
if right.val != 9:
left = right
right = right.next if right.val != 9:
right.val += 1
else:
left.val += 1
right = left.next
while right:
right.val = 0
right = right.next return 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 = ListNode(0)
curr = head
while curr:
dummy.next, curr.next, curr = curr, dummy.next, curr.next
return dummy.next rev_head = reverseList(head)
curr, carry = rev_head, 1
while curr and carry:
curr.val += carry
carry = curr.val / 10
curr.val %= 10
if carry and curr.next is None:
curr.next = ListNode(0)
curr = curr.next return reverseList(rev_head)
C++:
class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) return head;
ListNode *rev_head = reverse(head), *cur = rev_head, *pre = cur;
int carry = 1;
while (cur) {
pre = cur;
int t = cur->val + carry;
cur->val = t % 10;
carry = t / 10;
if (carry == 0) break;
cur = cur->next;
}
if (carry) pre->next = new ListNode(1);
return reverse(rev_head);
}
ListNode* reverse(ListNode *head) {
if (!head) return head;
ListNode *dummy = new ListNode(-1), *cur = head;
dummy->next = head;
while (cur->next) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = dummy->next;
dummy->next = t;
}
return dummy->next;
}
};
C++: Recursive
class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) return head;
int carry = helper(head);
if (carry == 1) {
ListNode *res = new ListNode(1);
res->next = head;
return res;
}
return head;
}
int helper(ListNode *node) {
if (!node) return 1;
int carry = helper(node->next);
int sum = node->val + carry;
node->val = sum % 10;
return sum / 10;
}
};
类似题目：