LeetCode2之两数相加(Add Two Numbers)

一、题目
请输入图片描述

二、一种解题思路

1)介绍:暴力解法(感觉没别的了吧,可能是我笨吧,原地爆炸下)

     方法思路:一路遍历,一路加,遇到一个链表的next为null时,则停止遍历该链表,并且让另一个链表的剩余节点和0相加。若链表已经遍历完了,还存在进位数,则在创建一个next节点。

   时间复杂度:O(Max(m,n))

   空间复杂度:O(Max(m,n))或O(Max(m,n)+1)

2)核心代码:

/**
 * 2:两数之和
 */
public class AddTwoNums {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode target = head;
        ListNode x = l1;
        ListNode y = l2;
        int num1;
        int num2;
        int sum = 0;
        //进位的值
        int carry = 0;
        while (x != null || y != null) {
            //规避某一个链表没有next的情况
            num1 = (x != null) ? x.val : 0;
            num2 = (y != null) ? y.val : 0;
            sum = num1 + num2 + carry;
            carry = sum / 10;
            target.next = new ListNode(sum % 10);
            target = target.next;
            if (x != null) {
                x = x.next;
            }
            if (y != null) {
                y = y.next;
            }
        }
        //排除链表最后一位出现进位的情况
        if (carry > 0) {
            target.next = new ListNode(carry);
        }
        return head.next;
    }
}

3)辅助类:

public class ListNode {
    public int val;
    public ListNode next;
 
    public ListNode(int x) {
        val = x;
        next = null;
    }
 
    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val + "}";
    }
}

三、LeetCode成功截图

请输入图片描述

四、感想

感觉自己还没做到最好,希望大家有好方法指教下,加油,加油,再加油,坚持,坚持,再坚持。

Last modification:October 25th, 2019 at 12:42 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment