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
C Solution:
Dummy head.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *reverse(struct ListNode *head) {
struct ListNode *res = 0;
while (head) {
struct ListNode *next = head->next;
head->next = res;
res = head;
head = next;
}
return res;
}
struct ListNode* plusOne(struct ListNode* head) {
head = reverse(head);
int carry = 1;
struct ListNode dummy, *p = &dummy;
p->next = head;
while (p->next && carry) {
p->next->val += carry;
carry = p->next->val / 10;
p->next->val %= 10;
p = p->next;
}
if (p->next) return reverse(head);
if (carry) {
p->next = malloc(sizeof(struct ListNode));
p->next->val = 1;
p->next->next = 0;
}
return reverse(head);
}
Double pointer.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *reverse(struct ListNode *head) {
struct ListNode *res = 0;
while (head) {
struct ListNode *next = head->next;
head->next = res;
res = head;
head = next;
}
return res;
}
struct ListNode* plusOne(struct ListNode* head) {
head = reverse(head);
int carry = 1;
struct ListNode **p = &head;
while (*p && carry) {
(*p)->val += carry;
carry = (*p)->val / 10;
(*p)->val %= 10;
p = &((*p)->next);
}
if (*p) return reverse(head);
if (carry) {
*p = malloc(sizeof(struct ListNode));
(*p)->val = 1;
(*p)->next = 0;
}
return reverse(head);
}
Better.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* plusOne(struct ListNode* head) {
struct ListNode *dummy = malloc(sizeof(struct ListNode));
dummy->val = 0;
dummy->next = head;
struct ListNode *l = dummy, *r = dummy;
while (r->next) {
if (r->next->val != 9) {
l = r->next;
}
r = r->next;
}
if (r->val != 9) {
r->val++;
return head;
}
l->val++;
l = l->next;
while (l) {
l->val = 0;
l = l->next;
}
if (dummy->val) return dummy;
return head;
}
Python Solution 1:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def plusOne(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def reverse(head):
head, tail = None, head
while tail:
head, tail.next, tail = tail, head, tail.next
return head
cur = head = reverse(head)
carry = 1
while cur and carry:
cur.val += 1
carry = cur.val // 10
cur.val %= 10
cur = cur.next
head = reverse(head)
if carry:
new_head = ListNode(1)
new_head.next = head
return new_head
return head
Python Solution 2:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def plusOne(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
l = r = dummy
while r.next:
if r.next.val != 9:
l = r.next
r = r.next
if r.val != 9:
r.val += 1
return head
l.val += 1
while l.next:
l.next.val = 0
l = l.next
if dummy.val == 1: return dummy
return head
Summary:
- dummy head and double pointer can both be used when the pre-element need some operations.
- The first two: 3ms, 0%
- The thired: 0ms, 0%
LeetCode: 369. Plus One Linked List
近期评论