# 445.两个链表相加
# 题目
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
# 解法
由于需要从低位开始加，然后进位。 因此可以采用栈来简化操作。 依次将两个链表的值分别入栈 stack1 和 stack2，然后相加入栈 stack，进位操作用一个变量 carried 记录即可。 最后根据 stack 生成最终的链表即可。
TIP
也可以先将两个链表逆置，然后相加，最后将结果再次逆置。
# 关键点解析
栈的基本操作 carried 变量记录进位 循环的终止条件设置成stack.length > 0 可以简化操作 注意特殊情况， 比如 1 + 99 = 100
# 具体代码
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
let m = [];
let n = [];
let k = [];
let cur1 = l1;
let cur2 = l2;
let jw = 0;
while(cur1){
m.push(cur1.val)
cur1 = cur1.next
}
while(cur2){
n.push(cur2.val)
cur2 = cur2.next
}
let ans = null
while(m.length > 0 || n.length > 0){
let x = Number(m.pop()) || 0
let y = Number(n.pop()) || 0
k.push((x+y+jw)%10)
let cur = (x+y+jw)%10
if(x+y+jw >= 10){
jw = 1
}else{
jw = 0
}
let curnode = new ListNode(cur)
curnode.next = ans
ans = curnode
}
let l = new ListNode(1)
if(jw == 1){
l.next = ans
return l
}
return ans
// if(jw == 1){
// k.push(1)
// }
// const dummy = {};
// let current = dummy;
// while (k.length > 0) {
// current.next = {
// val: k.pop(),
// next: null
// };
// current = current.next;
// }
// console.log(dummy.next)
// return dummy.next;
};
# 补链表逆转
好理解的双指针 定义两个指针： prepre 和 curcur ；prepre 在前 curcur 在后。 每次让 prepre 的 nextnext 指向 curcur ，实现一次局部反转 局部反转完成之后， prepre 和 curcur 同时往前移动一个位置 循环上述过程，直至 prepre 到达链表尾部
代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = NULL, *pre = head;
while (pre != NULL) {
ListNode* t = pre->next;
pre->next = cur;
cur = pre;
pre = t;
}
return cur;
}
};
简洁的递归 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 retret . 此后，每次函数在返回的过程中，让当前结点的下一个结点的 nextnext 指针指向当前节点。 同时让当前结点的 nextnext 指针指向 NULLNULL ，从而实现从链表尾部开始的局部反转 当递归函数全部出栈后，链表反转完成。
代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* ret = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return ret;
}
};
妖魔化的双指针 原链表的头结点就是反转之后链表的尾结点，使用 headhead 标记 . 定义指针 curcur，初始化为 headhead . 每次都让 headhead 下一个结点的 nextnext 指向 curcur ，实现一次局部反转 局部反转完成之后，curcur 和 headhead 的 nextnext 指针同时 往前移动一个位置 循环上述过程，直至 curcur 到达链表的最后一个结点 .
代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) { return NULL; }
ListNode* cur = head;
while (head->next != NULL) {
ListNode* t = head->next->next;
head->next->next = cur;
cur = head->next;
head->next = t;
}
return cur;
}
};