[LeetCode] 369. Plus One Linked List 链表加一运算
2024-10-21 09:39:02
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;
}
};
类似题目：
All LeetCode Questions List 题目汇总
最新文章
- test hypertext links for validity, accessibility, and recent modification
- 如何禁止 Mac OS X 在外接设备上生成 .DS_Store 文件？以及如何批量删除 .DS_Store 文件？
- Mysql中用SQL增加、删除字段，修改字段名、字段类型、注释，调整字段顺序总结
- springmvc下实现登录验证码功能
- apache ab压力测试报错（apr_socket_recv: Connection reset by peer (104)）
- C# 如何执行bat文件 传参数
- 20145129 《Java程序设计》第6周学习总结
- 【基础练习】【vector】codevs3393 序列倒置
- javascript 高级程序设计学习笔记（面向对象的程序设计)继承
- JQuery 模糊匹配
- 简学Python第二章__巧学数据结构文件操作
- Mysql--七种 Join 查询
- Luogu3605 [USACO17JAN]Promotion Counting晋升者计数
- Modbus库开发笔记之二：Modbus消息帧的生成
- IDEA项目的复制操作
- Jmeter学习之-获取登录的oken值（1）
- 提取IPv6地址的编码信息
- HGOI 20181103 题解
- Magento模型与ORM基础
- javaScript语言的预编译与运行