LeetCode369 用一个非空单链表来表示一个非负整数,然后将这个整数加一。你可以假设这个整数除了 0 本身,没有任何前导的 0.这个证书的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。
示例:
输入:[1,2,3]
输出:[1,2,4]
计算是从低位开始的,而链表是从高位开始的,所以要处理就必须反转过来,此时可以使用栈,也可以使用链表反转来实现。
基于栈
public ListNode plusOne(ListNode head) {
Stack<Integer> st = new Stack();
while (head != null) {
st.push(head.val);
head = head.next;
}
int carry = 0;
ListNode dummy = new ListNode(0);
int adder = 1;
while (!st.empty() || adder != 0 || carry > 0) {
int digit = st.empty() ? 0 : st.pop();
int sum = digit + adder + carry;
carry = sum >= 10 ? 1 : 0;
sum = sum >= 10 ? sum - 10 : sum;
ListNode cur = new ListNode(sum);
cur.next = dummy.next;
dummy.next = cur;
adder = 0;
}
return dummy.next;
}
这里一步一步来,现在输入[1,2,3],将他们全部压入栈中,设定dummy虚拟头结点,carry指的是进位1,adder代表的是要加的数,进入while后,digit指的是从栈中弹出的数,让sum等于digit+adder+carry,sum是到时候要在链表数据域展示的,如果sum是≥10的,那么进位就要变为1,但是在当前循环,在当前这个结点的数据域要展示的是个位,进位的1给到下一次循环,也就是更高位数来处理,在这里是十位,然后创建这个节点,cur.next = dummy.next
,dummy.next = cur
这两行代码做到的是让当前节点介入到虚拟头结点的后边,并且可以做到每一次都是往虚拟头结点的后面添加节点,这样就实现了将原链表压入栈中,从后边来处理,最后再返回已经进行了加1的链表的头部。文章来源:https://www.toymoban.com/news/detail-631907.html
基于链表反转实现
如果这里不使用栈,使用链表反转来实现该怎么做呢?很显然,我们先将原始链表反转,这方面完成加1和进位等处理,完成之后再次反转。文章来源地址https://www.toymoban.com/news/detail-631907.html
public ListNode plusOne2(ListNode head) {
ListNode reversed = reverseList(head); // 反转链表
ListNode cur = reversed;
int carry = 1;
while (cur != null) {
int sum = cur.val + carry;
carry = sum / 10;
cur.val = sum % 10;
if (carry == 0) {
break;
}
// 这里是到了最后一位的时候。下一位为空,还需要进位,所以在后面新加一个节点
if (cur.next == null) {
cur.next = new ListNode(0);
}
cur = cur.next;
}
ListNode result = reverseList(reversed); // 再次反转链表
return result;
}
public 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;
}
到了这里,关于算法通关村第二关——单链表加一的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!