Leetcode 题解 - 链表-(7)-链表求和 leetcode

[LeetCode] Add Two Numbers II 两个数字相加之二 【Leetcode 题解 - 链表-(7)-链表求和】
You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
翻转链表的话想到能有栈和递归两种
这道题是之前那道Add Two Numbers的拓展，我们可以看到这道题的最高位在链表首位置，如果我们给链表翻转一下的话就跟之前的题目一样了，这里我们来看一些不修改链表顺序的方法。由于加法需要从最低位开始运算，而最低位在链表末尾，链表只能从前往后遍历，没法取到前面的元素，那怎么办呢？我们可以利用栈来保存所有的元素，然后利用栈的后进先出的特点就可以从后往前取数字了，我们首先遍历两个链表，将所有数字分别压入两个栈s1和s2中，我们建立一个值为0的res节点，然后开始循环，如果栈不为空，则将栈顶数字加入sum中，然后将res节点值赋为sum%10，然后新建一个进位节点head，赋值为sum/10，如果没有进位，那么就是0，然后我们head后面连上res，将res指向head，这样循环退出后，我们只要看res的值是否为0，为0返回res->next，不为0则返回res即可，参见代码如下：

/** * Definition for singly-linked list. * public class ListNode { *int val; *ListNode next; *ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //栈来反转链表 Stack s1= new Stack<>(); Stack s2 = new Stack<>(); while(l1 != null){ s1.push(l1.val); l1 = l1.next; } while(l2 != null){ s2.push(l2.val); l2 = l2.next; }int sum = 0; ListNode p1 = new ListNode(0); while(!(s1.isEmpty() && s2.isEmpty())){ if(!s1.isEmpty()){ sum += s1.pop(); } if(!s2.isEmpty()){ sum += s2.pop(); }p1.val = sum % 10; ListNode p2 = new ListNode(sum / 10); p2.next = p1; p1 = p2; sum /=10; } return sum == 0 ? p1.next : p1; //注意返回值考虑进不进位 } }

下面这种方法使用递归来实现的，我们知道递归其实也是用栈来保存每一个状态，那么也就可以实现从后往前取数字，我们首先统计出两个链表长度，然后根据长度来调用递归函数，需要传一个参数差值，递归函数参数中的l1链表长度长于l2，在递归函数中，我们建立一个节点res，如果差值不为0，节点值为l1的值，如果为0，那么就是l1和l2的和，然后在根据差值分别调用递归函数求出节点post，然后要处理进位，如果post的值大于9，那么对10取余，且res的值自增1，然后把pos连到res后面，返回res，最后回到原函数中，我们仍要处理进位情况，参见代码如下：
这里明确几点：
1. addTwoNumbers里面也需要考虑进位的情况比如[5],[5] 这种在help函数里面是不存在post的无法考虑到进位或者说[9,2][9]这中情况也是
2.help函数处理直接相加的节点 res 和其next节点 post 根据post的值考虑进位的情况

/** * Definition for singly-linked list. * public class ListNode { *int val; *ListNode next; *ListNode(int x) { val = x; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int length1= sumLength(l1), length2 = sumLength(l2); int diff = length1 - length2; ListNode head = new ListNode(1); head.next = diff > 0 ? help(l1, l2, diff) : help(l2,l1, -diff); if(head.next.val > 9){ head.next.val %= 10; return head; } return head.next; } private int sumLength(ListNode node){ int sum = 0; while(node.next != null){ node = node.next; sum++; } return sum; } private ListNode help(ListNode l1, ListNode l2, int diff){ if(l1 == null) return null; ListNode res = diff == 0 ? new ListNode(l1.val + l2.val) : new ListNode(l1.val); ListNode post = diff == 0 ? help(l1.next, l2.next, 0) : help(l1.next, l2, diff - 1); if(post != null && post.val > 9){ post.val %= 10; res.val++; } res.next = post; return res; } }