LeetCode2之两数相加(Add Two Numbers)

本是古典何须时尚 2022-04-22 00:36 192阅读 0赞

一、题目

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyZWVfaWZjb25maWc_size_16_color_FFFFFF_t_70][]

二、一种解题思路

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成功截图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyZWVfaWZjb25maWc_size_16_color_FFFFFF_t_70 1][]

四、感想

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyZWVfaWZjb25maWc_size_16_color_FFFFFF_t_70]: /images/20220422/2ce067209a264e8491f58a253dab4e93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RyZWVfaWZjb25maWc_size_16_color_FFFFFF_t_70 1]: /images/20220422/3917ecfd911c480887e9f7a5c8f8df41.png