【Hot100】LeetCode—2. 两数相加

发布于:2024-08-20 ⋅ 阅读:(134) ⋅ 点赞:(0)



1- 思路

思路

分为几个步骤 ①数据结构:遍历指针,进位符②遍历两个链表③处理最后的进位符

  • 1- 数据结构
    • 定义 curAcurB 用来遍历两个链表
    • 定义 carry 记录进位
  • 2- 遍历两个链表
    • 通过中间变量,读取,若当前节点不为 null则读取值
    • 计算当前 nowNode
    • 计算进位值 carry
  • 3- 处理最终结果
    • 判断是否有进位值

2- 实现

⭐2. 两数相加——题解思路

在这里插入图片描述

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode curA = l1;
        ListNode curB = l2;

        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        int carry = 0;
        while(curA!=null || curB!=null){
            int v1 = curA==null? 0:curA.val;
            int v2 = curB==null? 0:curB.val; 
            int sum = v1+v2+carry;
            carry = sum/10;
            int now = sum%10;

            ListNode newNode = new ListNode(now);
            cur.next = newNode;

            cur = cur.next;
            if(curA!=null) curA = curA.next;
            if(curB!=null) curB = curB.next;
            
        }
        if(carry!=0){
            cur.next = new ListNode(carry);
        }

        return dummyHead.next;
    }
}

3- ACM 实现

public class twoSum {

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

    public static ListNode twoSum(ListNode head1,ListNode head2){
        ListNode curA = head1;
        ListNode curB = head2;

        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        int carry = 0;

        while(curA!=null || curB!=null){
            int val1 = curA == null? 0: curA.val;
            int val2 = curB == null? 0: curB.val;

            int nowNode = (val1+val2+carry)%10;
            carry = (val1+val2+carry)/10;

            cur.next = new ListNode(nowNode);
            cur = cur.next;
            if(curA!=null) curA = curA.next;
            if(curB!=null) curB = curB.next;
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
// 读取第一个链表的节点数量
        int n1 = sc.nextInt();
        ListNode head1 = null, tail1 = null;
        for (int i = 0; i < n1; i++) {
            int val = sc.nextInt();
            ListNode newNode = new ListNode(val);
            if (head1 == null) {
                head1 = newNode;
                tail1 = newNode;
            } else {
                tail1.next = newNode;
                tail1 = newNode;
            }
        }

// 读取第二个链表的节点数量
        int n2 = sc.nextInt();
        ListNode head2 = null, tail2 = null;
        for (int i = 0; i < n2; i++) {
            int val = sc.nextInt();
            ListNode newNode = new ListNode(val);
            if (head2 == null) {
                head2 = newNode;
                tail2 = newNode;
            } else {
                tail2.next = newNode;
                tail2 = newNode;
            }
        }
        ListNode forRes = twoSum(head1,head2);
        while (forRes!=null){
            System.out.print(forRes.val + " ");
            forRes = forRes.next;
        }
    }
}

网站公告

今日签到

点亮在社区的每一天
去签到