Leetcode之369-链表加1

前言

个人网站

公众号: 北京程序猿, 网站 : https://yaml.vip

算法题

题干

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.

示例

Input:
1->2->3

Output:
1->2->4

解法

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

Java代码

解法2代码

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代码

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代码

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 链表加一运算

本文著作权归作者所有。

商业转载请联系作者获得授权，非商业转载请于文首标明作者姓名，保持文章完整性，并附上出处和文章链接！未按规范转载者，作者保留追究相应责任的权利！

作者：北京程序猿

链接： 链表加1