LeetCode刷题笔记(二）两数相加

系统管理员 2022-05-27 08:17 198阅读 0赞

题目：

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

ListNode类

public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

解法：

class Solution {
        ListNode result = new ListNode(0);  //定义计算结果的node
        ListNode head = result;             //头节点
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            add(l1,l2,0);
            return head.next;
        }
         //递归计算   addNumber是进位
        public void add(ListNode l1, ListNode l2,int addNumber){
            if(l1 != null || l2 != null){
                int num = (l1==null?0:l1.val) + (l2==null?0:l2.val) + addNumber;    
                addNumber = num/10;     //计算进位
                num = num%10;     
                ListNode node = new ListNode(num);
                result.next = node;    
                result = node;
                add(l1==null?l1:l1.next,l2==null?l2:l2.next,addNumber);
            }else if(addNumber!=0){
                result.next = new ListNode(addNumber);
            }   
        }   
    }

算法如上，从头节点开始递归进行加法，进位赋值给addNumber,个位数部分创建新的节点，让result节点的next指向新的节点，再把result节点更换为新节点，进行下一次计算，当两个节点都为空的时候，退出递归。

注意点：两个链表长度不一样时要进行判断，如果节点为null，补0计算。退出递归时，要把最后的进位加上。

时间复杂度：O(n)；

空间复杂度：O(n);