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）