题目：

给你一个 非空 链表的头节点 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）