T O P

[资源分享]     算法5: LeetCode_单链表_两数相加

  • By - 楼主

  • 2022-11-25 00:02:02
    • 题目:
    • * 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
    • * 请你将两个数相加,并以相同形式返回一个表示和的链表。
    • * 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

     

    本题为力扣原题,链接为 https://leetcode.cn/problems/add-two-numbers/,具体例子参照原题给的demo

      解题思路:

    • 两个单链表中的整数相加,涉及到相加和超过10,需要向前进一位
    • 两个链表是否等长需要判断,如果不等长度,需要先计算等长部分,超出的部分需要根据思路1得出的结果判读。也就是前一位相加和满足进位,则继续计算;反之,则停止

     

     

    package code.code_02;
    
    /**
     * 力扣原题 https://leetcode.cn/problems/add-two-numbers/
     * 题目:
     * 给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
     * 请你将两个数相加,并以相同形式返回一个表示和的链表。
     * 你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
     *
     * demo1
     * 输入:l1 = [2,4,3], l2 = [5,6,4]
     * 输出:[7,0,8]
     * 解释:342 + 465 = 807.
     *
     * demo2
     * 输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
     * 输出:[8,9,9,9,0,0,0,1]
     *
     * 提示信息是:
     * 每个链表中的节点数在范围 [1, 100] 内
     * 0 <= Node.val <= 9
     * 题目数据保证列表表示的数字不含前导零
     *
     * 解题思路
     * 1, 两两相加,涉及到和超过10进位数
     * 2, 涉及到两个链表长度不等
     * 3, 可以补全两个链表,和单独生成一个新链表,但是浪费空间;
     * 4; 可以把两数之和压入长链表中,逢十进一
     *
     */
    public class NodeListAddTest {
    
        //链表
        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; }
        }
    
        public int length (ListNode node, int size)
          {
              while (node != null) {
                  size++;
                  node = node.next;
              }
              return size;
          }
    
        //获取链表长度_递归方式
      /* public int length (ListNode node, int size)
        {
            if (node == null) {
                return size;
            }
            size++;
            return node.next != null ? length(node.next, size) : size;
        }*/
    
    
        public ListNode addTwoNumbers(ListNode l1, ListNode l2)
        {
            int length1 = this.length(l1, 0);
            int length2 = this.length(l2, 0);
    
            ListNode lNode = length1 < length2 ? l2 : l1; //长链表
            ListNode sNode = (lNode == l1) ? l2 : l1;   //短链表
            ListNode prev = null;
    
            int carry = 0; //进位
            ListNode node = lNode;
    
            //根据短链表进行循环
            while (sNode != null) {
                int total = sNode.val + lNode.val + carry;
                lNode.val = total % 10; //更新后,长链表当前位置的新值
                carry = total/10; //如果是1, 则需要进位
                if (lNode.next == null) {
                    prev = lNode;
                }
                lNode = lNode.next;
                sNode = sNode.next;
            }
    
            //有可能两个链表长度不一致,此时长链表需要继续.
            while (lNode != null) {
                if (carry != 1) {
                    break;
                }
                int total = lNode.val + carry;
                lNode.val = total % 10; //更新后,长链表当前位置的新值
                carry = total/10; //如果是1, 则需要进位
                if (lNode.next == null) {
                    prev = lNode;
                }
                lNode = lNode.next;
            }
    
            //如果长链表最后一位数处理完还需要进位,则追加节点
            if (carry == 1) {
                ListNode tempNode = new ListNode(carry);
                prev.next = tempNode;
            }
    
            return node;
        }
    
        // 先设计打印方法,方便检查逆转后结果
        public void printNode (ListNode node)
        {
            if (node == null) {
                System.out.println("链表不存在");
            }
            System.out.println("当前节点的值为: " + node.val);
            //递归的方式逐层打印Node的子节点
            if(node.next != null) {
                printNode(node.next);
            }
        }
    
        public static void main(String[] args) {
            NodeListAddTest test = new NodeListAddTest();
            //链表1
            ListNode l1 = test.new ListNode(2);
            l1.next = test.new ListNode(4);
            l1.next.next = test.new ListNode(3);
    
            //链表2
            ListNode l2 = test.new ListNode(5);
            l2.next = test.new ListNode(6);
            l2.next.next = test.new ListNode(4);
    
    
            ListNode nodeList = test.addTwoNumbers(l1, l2);
            test.printNode(nodeList);
    
        }
    }

     

     

    力扣测试结果:

     

    本帖子中包含资源

    您需要 登录 才可以下载,没有帐号?立即注册