leetcode每日一题.445:两数相加II

小鱼儿 2023-07-25 11:20 12阅读 0赞

### 题目描述： ###

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
    
    你可以假设除了数字 0 之外，这两个数字都不会以零开头。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/add-two-numbers-ii
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

###### 进阶： ######

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

###### 示例： ######

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 8 -> 0 -> 7

##### 分析： #####

比较简单的办法就是遍历两个链表，然后生成两个整数，再把两个整数相加，最后再把整数拆分成链表。但是这样的话如果链表长度很长就会整数溢出或者超出时间限制。因为此题是单向链表，并且需要把尾部当作低位来相加，就是逆序，所以可以用栈（Stack）来做，因为栈是先进后出，符合此题要求。  
代码如下：

###### java： ######

/** * 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) { 
        	// 定义返回结果链表和栈
            ListNode res = null;
            Stack<Integer> s1 = new Stack<>();
            Stack<Integer> s2 = new Stack<>();
            // 遍历链表，把值压栈
            while (l1 != null) { 
                s1.push(l1.val);
                l1 = l1.next;
            }
            while (l2 != null) { 
                s2.push(l2.val);
                l2 = l2.next;
            }
            int carry = 0;
            while (!s1.isEmpty() || !s2.isEmpty() || carry > 0) { 
            	// 由于栈是FILO（先进后出）所以每次弹栈都是从低位->高位
                int sum = (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop()) + carry;
                ListNode temp = new ListNode(sum % 10);
                carry = sum / 10;
                // 链表的头插法
                temp.next = res;
                res = temp;
            }
            return res;
        }
    }

###### python： ######

# Definition for singly-linked list.
    # class ListNode:
    # def __init__(self, x):
    # self.val = x
    # self.next = None
    
    class Solution:
        def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
            s1, s2, res = [], [], None
            while l1:
                s1.append(l1.val)
                l1 = l1.next
            while l2:
                s2.append(l2.val)
                l2 = l2.next
            carry = 0
            while s1 or s2 or carry > 0:
                sum = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
                temp = ListNode(sum % 10)
                temp.next = res
                res = temp
                carry = sum // 10
            return res

##### 总结： #####

链表的常规题目，需要了解栈以及链表的头插法、尾插法。