[LeetCode] Plus One Linked List 链表加一运算

时间:2022-09-21 15:34:33

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]

这道题给了我们一个链表,用来模拟一个三位数,表头是高位,现在让我们进行加1运算,这道题的难点在于链表无法通过坐标来访问元素,只能通过遍历的方式进行,而这题刚好让我们从链尾开始操作,从后往前,遇到进位也要正确的处理,最后还有可能要在开头补上一位。那么我们反过来想,如果链尾是高位,那么进行加1运算就方便多了,直接就可以边遍历边进行运算处理,那么我们可以做的就是先把链表翻转一下,然后现在就是链尾是高位了,我们进行加1处理运算结束后,再把链表翻转回来即可,参见代码如下:

解法一:

class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) return head;
ListNode *rev_head = reverse(head), *cur = rev_head, *pre = cur;
int carry = ;
while (cur) {
pre = cur;
int t = cur->val + carry;
cur->val = t % ;
carry = t / ;
if (carry == ) break;
cur = cur->next;
}
if (carry) pre->next = new ListNode();
return reverse(rev_head);
}
ListNode* reverse(ListNode *head) {
if (!head) return head;
ListNode *dummy = new ListNode(-), *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;
}
};

我们也可以通过递归来实现,这样我们就不用翻转链表了,通过递归一层一层的调用,最先处理的是链尾元素,我们将其加1,然后看是否有进位,返回进位,然后回溯到表头,加完进位,如果发现又产生了新的进位,那么我们在最开头加上一个新节点即可,参见代码如下:

解法二:

class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) return head;
int carry = helper(head);
if (carry == ) {
ListNode *res = new ListNode();
res->next = head;
return res;
}
return head;
}
int helper(ListNode *node) {
if (!node) return ;
int carry = helper(node->next);
int sum = node->val + carry;
node->val = sum % ;
return sum / ;
}
};

下面这种方法比较巧妙了,思路是遍历链表,找到右起第一个不为9的数字,如果找不到这样的数字,说明所有数字均为9,那么在表头新建一个值为0的新节点,进行加1处理,然后把右边所有的数字都置为0即可。举例来说:

比如1->2->3,那么第一个不为9的数字为3,对3进行加1,变成4,右边没有节点了,所以不做处理,返回1->2->4。

再比如说8->9->9,找第一个不为9的数字为8,进行加1处理变成了9,然后把后面的数字都置0,得到结果9->0->0。

再来看9->9->9的情况,找不到不为9的数字,那么再前面新建一个值为0的节点,进行加1处理变成了1,把后面的数字都置0,得到1->0->0->0。

解法三:

class Solution {
public:
ListNode* plusOne(ListNode* head) {
ListNode *cur = head, *right = NULL;
while (cur) {
if (cur->val != ) right = cur;
cur = cur->next;
}
if (!right) {
right = new ListNode();
right->next = head;
head = right;
}
++right->val;
cur = right->next;
while (cur) {
cur->val = ;
cur = cur->next;
}
return head;
}
};

最后这种解法是解法二的迭代写法,我们用到栈,利用栈的先进后出机制,就可以实现从后往前的处理节点,参见代码如下:

解法四:

class Solution {
public:
ListNode* plusOne(ListNode* head) {
stack<ListNode*> s;
ListNode *cur = head;
while (cur) {
s.push(cur);
cur = cur->next;
}
int carry = ;
while (!s.empty() && carry) {
ListNode *t = s.top(); s.pop();
int sum = t->val + carry;
t->val = sum % ;
carry = sum / ;
}
if (carry) {
ListNode *new_head = new ListNode();
new_head->next = head;
head = new_head;
}
return head;
}
};

类似题目:

Plus One

参考资料:

https://leetcode.com/problems/plus-one-linked-list/

https://leetcode.com/discuss/111165/2-accepted-java-solution

https://leetcode.com/discuss/111205/simple-solution-use-recursion

https://leetcode.com/discuss/111157/9-lines-recursive-without-helper

https://leetcode.com/discuss/111155/java-stack-solution-with-inline-explanation

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] Plus One Linked List 链表加一运算的更多相关文章

  1. &lbrack;LeetCode&rsqb; 369&period; Plus One Linked List 链表加一运算

    Given a non-negative number represented as a singly linked list of digits, plus one to the number. T ...

  2. Leetcode 234 Palindrome Linked List 链表

    判断链表是否是回文. 我直接将链表的一半进行倒置,然后将两半的链表进行比较 /** * Definition for singly-linked list. * struct ListNode { * ...

  3. Leetcode 206 Reverse Linked List 链表

    将单向链表反转 完成如图操作,依次进行即可 1 2 3 /** * Definition for singly-linked list. * struct ListNode { * int val; ...

  4. &lbrack;LeetCode&rsqb;206&period; Reverse Linked List&lpar;链表反转&rpar;

    Reverse a singly linked list. click to show more hints. Subscribe to see which companies asked this ...

  5. &lbrack;LeetCode&rsqb; 92&period; Reverse Linked List II 反向链表II

    Reverse a linked list from position m to n. Do it in-place and in one-pass. For example:Given 1-> ...

  6. LeetCode解题报告&colon;Linked List Cycle &amp&semi;&amp&semi; Linked List Cycle II

    LeetCode解题报告:Linked List Cycle && Linked List Cycle II 1题目 Linked List Cycle Given a linked ...

  7. LeetCode 上最难的链表算法题,没有之一!

    题目来源于 LeetCode 第 23 号问题:合并 K 个排序链表. 该题在 LeetCode 官网上有关于链表的问题中标注为最难的一道题目:难度为 Hard ,通过率在链表 Hard 级别目前最低 ...

  8. &lbrack;LeetCode&rsqb; 92&period; Reverse Linked List II&lowbar;Medium tag&colon; Linked List

    Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Exa ...

  9. 【python】Leetcode每日一题-旋转链表

    [python]Leetcode每日一题-旋转链表 [题目描述] 给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置. 示例1: 输入:head = [1,2,3,4,5] ...

随机推荐

  1. java web开发小细节

    <!--1. 在form表单中的action里用绝对路径而不是相对路径--> <form action="${basePath}loginForm" name=& ...

  2. Android 中布局设置导致的TextView不显示的问题

    将TextView放入TableLayout中,设置TextView的Layout Witdh/Layout Height 为Wrap Content或其他大小,导致TextView内容无法显示,改为 ...

  3. 什么是ECMA标准

    是1961年成立的旨在建立统一的电脑操作格式标准,包括程序语言和输入输出的组织. 官方ECMA标准列表: http://www.ecma-international.org/publications/ ...

  4. 模拟 ZOJ 3736 Pocket Cube

    题目传送门 题意:魔方最多旋转n次,问最多能使多少面颜色相同 分析:6种状态(3种旋转方式*顺逆方向,其他对称的!),首先先打个表,然后很愉快的DFS.自己写的时候费劲脑汁,代码很长,还TLE了... ...

  5. jQuery选择器介绍:基本选择器、层次选择器、过滤选择器、表单选择器

    选择器是jQuery的根基,在jQuery中,对事件处理.遍历DOM和Ajax操作都依赖于选择器.因此,如果能熟练的使用选择器,不仅能简化代码,而且可以达到事半功倍的效果.jQuery选择器完全继承了 ...

  6. float2int

    flaot转int时,会直接舍弃小数为,但是当把f所在的地址的数据当成int解析时,就是另外的情况了. #include<iostream> using namespace std; in ...

  7. h2database源码浅析:SQL语句的执行

    最近想好好了解一下数据库的原理,下载了h2database的源码,准备好好看看.此过程的一些想法,暂且记下来,权当做读码笔记吧! 为了调试准备的测试用例: @Test public void test ...

  8. Dijkstra算法and Floyd算法 HDU 1874 畅通工程续

    Dijkstra算法描述起来比较容易:它是求单源最短路径的,也就是求某一个点到其他各个点的最短路径,大体思想和prim算法差不多,有个数组dis,用来保存源点到其它各个点的距离,刚开始很好办,只需要把 ...

  9. python之路----线程

    线程概念的引入背景 进程 程序并不能单独运行,只有将程序装载到内存中,系统为它分配资源才能运行,而这种执行的程序就称之为进程.程序和进程的区别就在于:程序是指令的集合,它是进程运行的静态描述文本:进程 ...

  10. python-day27--configparser模块

    1.来看一个好多软件的常见文档格式如下: [DEFAULT] ServerAliveInterval = 45 Compression = yes CompressionLevel = 9 Forwa ...