leetcode2. 两数相加

题目描述

必威体育苹果app下载给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

必威体育苹果app下载你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例

输入:l1 = [2,4,3], l2 = [5,6,4]

输出:[7,0,8]

解释:342 + 465 = 807.

题目分析

加法运算,其中每个链表表示一个整数,以逆序存储,也就是说链表的head表示个位,按顺序遍历链表已是对齐状态,只需要考虑进位即可

解法1

必威体育苹果app下载链表可能不一样长,循环遍历链表对应部分,相加,存入result链表,考虑进位问题,然后将剩余部分放入result内,同时也需要考虑进位问题。最后还个小细节,什么时候我们需要提前new出next?就是还有下一个数需要放的时候,如果直接new出next不考虑条件,则结果尾部会多出一个0,时间复杂度O(n)。

/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode list = new ListNode(0);
     ListNode result = list;
     int value ;
     //循环共同部分
     while (null != l1 && null != l2) {
       value = (l1.val + l2.val) + list.val;
       list.val = value % 10;
       //只有后面还有数或者当前有进位时候才需要new出next
       if(null != l1.next || null != l2.next || value / 10 > 0) {
         list.next = new ListNode(value / 10);
         list = list.next;
       }
       l1 = l1.next;
       l2 = l2.next;
     }
     while (null != l1) {
       value = l1.val + list.val;
       list.val = value % 10;
       if(null != l1.next || value / 10 > 0) {
         list.next = new ListNode(value / 10);
         list = list.next;
       }
       l1 = l1.next;
     }
     while (l2 != null) {
       value = l2.val + list.val;
       list.val = value % 10;
       if(null != l2.next || value / 10 > 0) {
         list.next = new ListNode(value / 10);
         list = list.next;
       }
       l2 = l2.next;
     }
     return result;
    }
}

 

posted @ 2022-01-19 14:56  Carol淋  阅读(12)  评论(0编辑