“This is the third day of my participation in the November Gwen Challenge. See details of the event: The last Gwen Challenge 2021”.

Today we are going to look at the problem of adding two numbers in LeetCode

Topic describes

You are given two non-empty linked lists representing two non-negative integers. Each digit is stored in reverse order, and only one digit can be stored per node.

You add the two numbers and return a linked list representing the sum in the same form.

You can assume that neither of these numbers will start with 0, except for the number 0.

The subject sample

The title method

Solution 1: Recursive implementation (recommended)

Find the boundary values of the two input lists and the boundary values of the new list, allowing for carry implementation recursion.

Both time complexity and space complexity are O(n).

/** * Definition for singly-linked list. * 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; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) {if(l1 == null){return l1; } if(l2 == null){return l1; } int addSum = l1.val + l2.val; ListNode newNode = new ListNode(addSum % 10); Newnode. next = addTwoNumbers(l1.next, l2.next); int newCarry = addSum / 10; If (newCarry > 0){// Carry newNode.next = addTwoNumbers(newNode.next, new ListNode(newCarry)); } return newNode; }}Copy the code

Solution two: conventional traversal

Global head nodes and execution nodes are introduced, and the list of execution nodes is updated during traversal

Time and space are also O(n).

Class Solution {public ListNode addTwoNumbers(ListNode L1, ListNode l2) {// headNode = new ListNode(0); ListNode currentNode = headNode; // nextCarry value int nextCarry = 0; while(l1 ! = null || l2 ! = null){ int l1Val = l1 ! = null ? l1.val: 0; int l2Val = l2 ! = null ? l2.val: 0; Int addSum = l1Val + l2Val + nextCarry; currentNode.next = new ListNode(addSum % 10); currentNode = currentNode.next; nextCarry = addSum / 10; if(l1 ! = null){ l1 = l1.next; } if(l2 ! = null){ l2 = l2.next; } } if(nextCarry > 0){ currentNode.next = new ListNode(nextCarry); } return headNode.next; }}Copy the code

LeetCode: leetcode-cn.com/problems/ad…