【Check 41】2024-03-31 - 2. 两数相加

[larscheng]

2. 两数相加

[larscheng]

思路

• 方法一：双指针迭代两个链表节点，加和计算进位值 , O(n)/O(1)

• 方法二：递归计算两个链表节点和，O(n)/O(n)

  代码

  
  
  class Solution1 {
  
      //双指针迭代两个链表的节点，加和后计算位数值和进位值
      //O(n)/O(1)
      public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
          ListNode result = new ListNode();
          // 临时数据
          ListNode temp = result;
          int carry = 0;
          while (l1!=null||l2!=null){
              int a=0,b=0;
              if (l1!=null){
                  a = l1.val;
                  l1 = l1.next;
              }
              if (l2!=null){
                  b = l2.val;
                  l2 = l2.next;
              }
  
              int sum = carry+a+b;
              //进位
              carry = sum/10;
              //位数
              sum = sum%10;
              temp.next = new ListNode(sum);
              temp = temp.next;
          }
          if (carry>=1){
              temp.next = new ListNode(carry);
          }
  
          return result.next;
      }
  }

```java
class Solution {
      //递归，递归计算两节点值
    //O(n)/O(n)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return addTwo(l1, l2, 0);
    }

    private ListNode addTwo(ListNode l1, ListNode l2, int carry) {
        if (l1==null&&l2==null){
            return carry == 0 ? null : new ListNode(carry);
        }
        if (l1==null){
            //默认l1为基准长链表，如果l1比l2短，则交换以下
            l1=l2;
            l2=null;
        }
        carry += l1.val + (l2 == null ? 0 : l2.val);
        //修改l1链表值，最终返回链表l1
        l1.val = carry%10;
        //递归计算剩余节点
        l1.next = addTwo(l1.next,(l2==null?null:l2.next),carry/10);

        return l1;
    }
}

[larscheng]

链表相加（正序）

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 链表正序相加
     * 方法1：栈收集(会超时)
     * 方法2：先反转链表，再计算构造链表，最后再反转结果链表
     *
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        Stack<Integer> res = new Stack<>();
        while (head1 != null || head2 != null) {
            if (head1 != null) {
                stack1.push(head1.val);
                head1 = head1.next;
            }
            if (head2 != null) {
                stack2.push(head2.val);
                head2 = head2.next;
            }
        }

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            int num1 = stack1.isEmpty() ? 0 : stack1.pop();
            int num2 = stack2.isEmpty() ? 0 : stack2.pop();
            int sum  = carry + num1 + num2;
            carry = sum / 10;
            ListNode node = new ListNode(sum % 10);
            //cur-node1()-node2
            node.next = cur.next;
            cur.next = node;
        }
        return dummy.next;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode node1 = reverse(head1);
        ListNode node2 = reverse(head2);

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        int carry = 0;

        while (node1 != null || node2 != null || carry != 0) {
            int val1 = node1 == null ? 0 : node1.val;
            int val2 = node2 == null ? 0 : node2.val;
            int sum = carry + val1 + val2;
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if(node1!=null){
                node1 = node1.next;
            }
            if(node2!=null){
                node2 = node2.next;
            }
        }

        return reverse(dummy.next);
    }

    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next =  cur.next;
            //反转
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}