Leetcode之369-链表加1

算法题

题干

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.

示例

1
2
3
4
5
Input:
1->2->3

Output:
1->2->4

解法

  1. 链表与数组区别在于链表只能从前往后去遍历, 但加一行为是从表尾去操作, 往前进位非常不方便, 因此最直接的解法是将链表反转, 之前的表尾转换为表头, 从表头开始进行加一操作, 最后再将链表反转。
  2. 链表和二叉树都是特别适合递归的数据结构, 既然我们想操作表尾, 直接通过递归获取进位, 最后再考虑进位是否添加到表头。
  3. 非递归模式, 采用栈这种数据结构。
  4. 首先找到链表最后一个不为9的元素, 如果没有, 说明链表元素都为9, 在表头添加新节点(值为1), 后续所有节点值都赋值为1;如果找到, 当前节点值加1, 后续所有节点值同样赋值为0。

Java代码

解法2代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode recursionPlusOne(ListNode head) {
if (head == null) {
return null;
}
int carry = getCarrier(head);
if (carry == 1) {
ListNode root = new ListNode(carry);
root.next = head;
return root;
}
return head;
}

public int getCarrier(ListNode node) {
if (node == null) {
return 1;
}
int carry = getCarrier(node.next);
int sum = node.val + carry;
node.val = sum % 10;
return sum / 10;
}

代码解析

  1. 方法getCarrier采用递归获取进位, 退出条件是节点Node为null时返回加1操作的那个1。
  2. getCarrier方法后四行代码是将节点重新赋值, 并返回新的进位。

解法3代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode stackPlusOne(ListNode head) {
if (head == null) {
return null;
}
Stack<ListNode> stack = new Stack<>();
ListNode ele = head;
while (ele != null) {
stack.push(ele);
ele = ele.next;
}
int carry = 1;
while (!stack.isEmpty() && carry != 0) {
ListNode node = stack.pop();
int sum = node.val + carry;
node.val = sum % 10;
carry = sum / 10;
}
if (carry != 0) {
ListNode root = new ListNode(carry);
root.next = head;
head = root;
}
return head;
}

代码解析

  1. 第7-10行代码将链表元素入栈。
  2. 第12行carry!=0条件可提前终止循环, 没有进位时没必要进行后续操作。

解法4代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public ListNode plusOne(ListNode head) {
if (head == null) {
return null;
}
ListNode cursor = head, rightNotNineNode = null;
while (cursor != null) {
if (cursor.val != 9) {
rightNotNineNode = cursor;
}
cursor = cursor.next;
}
if (rightNotNineNode == null) {
rightNotNineNode = new ListNode(0);
rightNotNineNode.next = head;
head = rightNotNineNode;
}
rightNotNineNode.val += 1;
cursor = rightNotNineNode.next;
while (cursor != null) {
cursor.val = 0;
cursor = cursor.next;
}
return head;
}

代码解析

  1. 第5行代码rightNotNineNode表示链表从右边起第一个不为9的节点。
  2. 第6-11行代码获取rightNotNineNode值。
  3. 第12-16行代码是考虑链表中所有元素均为9, 在表头前添加新元素, 节点值为0, 并将新节点赋给rightNotNineNode。
  4. 第17行代码将rightNotNineNode节点值进行加1操作。
  5. 第18-22行代码将rightNotNineNode节点后续所有节点的值赋值为0。

解法4示例

  1. 1->2->3, 右起最后一个值不为9的节点为3, 节点值加1, 1->2->4。
  2. 1->2->9, 右起最后一个值不为9的节点为2, 节点值加1, 后续所有节点值赋值为0, 1->3->0。
  3. 9->9->9, 链表中没有一个值不为9的节点, 表头添加新节点值为0, 节点值加1, 后续所有节点值赋值为0, 1->0->0->0。

总结

  1. 这道题目是中等难度, 起始阶段仅想到解法1、2和3, 解法4想法很巧妙。
  2. Leetcode上本算法题显示This question is locked. Please subscribe to see this question.,所以就没进行代码测试用例的检验。

参考资料

  1. [LeetCode] Plus One Linked List 链表加一运算
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%