LeetCode 2816.翻倍以链表形式表示的数字

题目：

给你一个 非空 链表的头节点 head ，表示一个不含前导零的非负数整数。

将链表 翻倍 后，返回头节点 head 。

思路：

思路一：反转链表，两个相同的链表求和

思路二：如果不考虑进位，就是每个节点的值乘以 2。什么时候会受到进位的影响呢？只有下一个节点大于 4 的时候，才会因为进位多加一。特别地，如果链表头的值大于 4，那么需要在前面插入一个新的节点。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {  // 思路二
    public ListNode doubleIt(ListNode head) {
        if (head.val > 4) {
            head = new ListNode(0, head);
        }
        for (ListNode cur = head; cur != null; cur = cur.next) {
            cur.val = cur.val * 2 % 10;
            if (cur.next != null && cur.next.val > 4)
                cur.val++;
        }
        return head;
    }
}

性能：

时间复杂度 o（n）

空间复杂度 o（1）

原文地址：https://blog.csdn.net/qq_57349657/article/details/143858114

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！