NC189. 给单链表加一
描述
示例1
输入:
{1,2,3}
输出:
{1,2,4}
示例2
输入:
{1,2,0}
输出:
{1,2,1}
示例3
输入:
{9}
输出:
{1,0}
C++ 解法, 执行用时: 2ms, 内存消耗: 416KB, 提交时间: 2022-02-09
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/*
方法一：反转链表再相加
这个题可以看作是“链表反转”和“链表加法”两个题的结合：
1. 先做一个链表的反转，让高位在头，低位在尾；
2. 然后把1这个数字转化成一个只有一个节点的链表；
3. 将以上两个链表模拟竖式加法，做一个链表两数之和；
4. 最后把两数之和的链表反转过来返回。
*/
ListNode* plusOne1(ListNode* head) {
ListNode* head1 = reverseList(head);
ListNode* head2 = new ListNode(1);
return reverseList(addTwoNumbers(head1, head2));
}
/*
方法二：递归
*/
ListNode* plusOne(ListNode* head) {
int carry = helper(head);
if(carry != 0) {
ListNode* root = new ListNode(carry);
root->next = head;
return root;
}
return head;
}
private:
//方法一调用
ListNode* addTwoNumbers(ListNode* head1, ListNode* head2) {
ListNode *p1 = head1, *p2 = head2;
int carry = 0;
ListNode* dummy = new ListNode(-1);
ListNode* cur = dummy;
while(p1 != NULL || p2 != NULL){
int sum = carry + (p1 != NULL? p1->val: 0) + (p2 != NULL? p2->val: 0);
cur->next = new ListNode(sum % 10);
carry = sum / 10;
if(p1 != NULL) p1 = p1->next;
if(p2 != NULL) p2 = p2->next;
cur = cur->next;
}
if(carry > 0) cur->next = new ListNode(carry);
return dummy->next;
}
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* cur = head;
while(cur != NULL){
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
//方法二调用
int helper(ListNode *head) {
if(head == NULL) return 1;
int sum = head->val + helper(head->next);
head->val = sum % 10;
return sum / 10;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-03-14
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode* add1(ListNode* node,ListNode * parent){ // 节点和它的 父节点
if(!node -> next){ // 最后一个节点直接加1
node -> val ++;
}else{
add1(node->next, node); // 非最后一个递归向下
}
if(node -> val == 10){ // 进位
node -> val = 0;
if(parent){ // 有父节点
parent -> val ++;
}else{ // 根 无父节点
parent = new ListNode(1);
parent->next = node;
}
}
return parent?parent:node; // 根是否进位
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* plusOne(ListNode* head) {
return add1(head, NULL);
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-02-08
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* plusOne(ListNode* head)
{
ListNode *newHead = reverseList(head);
int remain = 1;
ListNode *cur = newHead;
ListNode *pre = cur;
while(cur)
{
remain += cur->val;
if(remain < 10)
{
cur->val = remain;
break;
}
else
{
cur->val = remain - 10;
remain = 1;
}
pre = cur;
cur = cur->next;
}
if(cur==NULL && remain != 0)
{
ListNode *newNode = new ListNode(remain);
pre->next = newNode;
}
return reverseList(newHead);
}
ListNode* reverseList(ListNode *head)
{
if(head == NULL || head->next == NULL)
return head;
ListNode *pre = NULL;
ListNode *cur = head;
ListNode *nxt = NULL;
while(cur->next)
{
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
cur->next = pre;
return cur;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2021-12-19
// 序号：00003，遍数：001
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* plusOne(ListNode* head) {
// write code here
int x = helper(head);
if(x != 0) {
ListNode* root = new ListNode(x);
root->next = head;
return root;
}
return head;
}
private:
int helper(ListNode *nd) {
if(nd == NULL) {
return 1;
}
int sum = nd->val + helper(nd->next);
nd->val = sum%10;
return sum/10;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2021-12-07
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* plusOne(ListNode* head) {
// write code here
if(head == NULL) return head;
int c = dfs(head);
if(c > 0)
{
ListNode* dummy = new ListNode(c);
dummy->next = head;
return dummy;
}
return head;
}
int dfs(ListNode* head)
{
if(head == NULL) return 1;
int c = dfs(head->next);
c += head->val;
if(c >= 10)
{
head->val = c%10;
return 1;
}
else
{
head->val = c;
return 0;
}
}
};