🍗[NC]317. 链表相加合集

🚩传送门：牛客题目
力扣题目

题1：链表相加 I

题目

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

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

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

数据范围：

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0] 输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

时间复杂度

时间复杂度：，其中 和 是链表的长度。

空间复杂度：

我的代码

    public ListNode ListAdd (ListNode l1, ListNode l2) {
        // write code here
        int sum=0;
        int carry=0;
        int l1val=0;
        int l2val=0;
        ListNode head=new ListNode(0);
        ListNode tail=head;
        ListNode pl1=l1;
        ListNode pl2=l2;
        while(pl1!=null && pl2!=null){
           sum=pl1.val+pl2.val+carry;         // 求和
           carry=sum/10;                         // 求进位
           tail.next=new ListNode(sum%10);   // 分配新结点,赋值
           tail=tail.next;                      // 尾指针指向新结点
           pl1=pl1.next;                     // 哨兵下行
           pl2=pl2.next;                     // 哨兵下行
        }
        while(pl1!=null){                     // pl1不空
            sum=carry+pl1.val;                 // 求和
            carry=sum/10;                     // 求进位
            tail.next=new ListNode(sum%10);  // 分配新结点,赋值
            pl1=pl1.next;                     // 哨兵下行
            tail=tail.next;                     // 尾指针指向新结点
        }
        while(pl2!=null){                     // pl2不空
            sum=carry+pl2.val;                 // 求和
            carry=sum/10;                     // 求进位
            tail.next=new ListNode(sum%10);  // 分配新结点,赋值
            pl2=pl2.next;                     // 哨兵下行
            tail=tail.next;                     // 尾指针指向新结点
        }
        if(carry!=0){                         // pl2和pl1同时空，但是进位仍在
            tail.next=new ListNode(carry);     // 分配新结点,赋值进位
            tail=tail.next;                     // 尾指针指向新结点
        }
        tail.next=null;                      // 将尾巴的下一个指针指向null
        return head.next;                     // 返回头结点后的第一个结点
    }
}

题2：链表相加 II

🚩传送门：牛客题目
力扣题目

题目

给定两个 非空 链表 l1 和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

数据范围：

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4] 输出：[7,8,0,7]

时间复杂度

时间复杂度：，其中 和 是链表的长度。

空间复杂度：

我的代码

public class Solution {
    // 翻转链表
    public ListNode reverse(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode pre=head;
        ListNode cur=head.next;
        ListNode next=null;
        pre.next=null;
        while(cur!=null){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
    // 链表相加
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        head1=reverse(head1);    // 反转
        head2=reverse(head2);    // 反转
        return reverse(ListAdd(head1,head2));    // 相加反转
    }
    public ListNode ListAdd (ListNode l1, ListNode l2) {
        // write code here
        int sum=0;
        int carry=0;
        int l1val=0;
        int l2val=0;
        ListNode head=new ListNode(0);
        ListNode tail=head;
        ListNode pl1=l1;
        ListNode pl2=l2;
        while(pl1!=null && pl2!=null){
           sum=pl1.val+pl2.val+carry;         // 求和
           carry=sum/10;                         // 求进位
           tail.next=new ListNode(sum%10);   // 分配新结点,赋值
           tail=tail.next;                      // 尾指针指向新结点
           pl1=pl1.next;                     // 哨兵下行
           pl2=pl2.next;                     // 哨兵下行
        }
        while(pl1!=null){                     // pl1不空
            sum=carry+pl1.val;                 // 求和
            carry=sum/10;                     // 求进位
            tail.next=new ListNode(sum%10);  // 分配新结点,赋值
            pl1=pl1.next;                     // 哨兵下行
            tail=tail.next;                     // 尾指针指向新结点
        }
        while(pl2!=null){                     // pl2不空
            sum=carry+pl2.val;                 // 求和
            carry=sum/10;                     // 求进位
            tail.next=new ListNode(sum%10);  // 分配新结点,赋值
            pl2=pl2.next;                     // 哨兵下行
            tail=tail.next;                     // 尾指针指向新结点
        }
        if(carry!=0){                         // pl2和pl1同时空，但是进位仍在
            tail.next=new ListNode(carry);     // 分配新结点,赋值进位
            tail=tail.next;                     // 尾指针指向新结点
        }
        tail.next=null;                      // 将尾巴的下一个指针指向null
        return head.next;                     // 返回头结点后的第一个结点
    }
}