LeetCode - Medium - 2. Add Two Numbers

以你之姓@ 2022-12-30 03:53 79阅读 0赞

## Topic ##

*  Math
 *  Linked List

## Description ##

[https://leetcode.com/problems/add-two-numbers/][https_leetcode.com_problems_add-two-numbers]

You are given two **non-empty** linked lists representing two non-negative integers. The digits are stored in **reverse order**, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

**Example 1**:

2->4->3
    +
    5->6->4
    =
    7->0->8
    
    Input: l1 = [2,4,3], l2 = [5,6,4]
    Output: [7,0,8]
    Explanation: 342 + 465 = 807.

**Example 2**:

Input: l1 = [0], l2 = [0]
    Output: [0]

**Example 3**:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    Output: [8,9,9,9,0,0,0,1]

**Constraints**:

*  The number of nodes in each linked list is in the range \[1, 100\].
 *  0 <= Node.val <= 9
 *  It is guaranteed that the list represents a number that does not have leading zeros.

## Analysis ##

加法运算规则，指针的操作。

## Submission ##

import com.lun.util.SinglyLinkedList.ListNode;
    
    public class AddTwoNumbers { 
    	
    	//方法一：假设l1,l2都是合法参数，返回新的链表
    	public ListNode addTwoNumbers1(ListNode l1, ListNode l2) { 
    		
    		//进位
    		int carry = 0;
    		
    		ListNode head = null, tail = null;
    		
    		while(l1 != null || l2 != null) { 
    			
    			int a = l1 != null ? l1.val : 0 ;
    			int b = l2 != null ? l2.val : 0;
    			
    			int sum = a + b + carry;
    			carry = sum / 10;
    			
    			ListNode tmp = new ListNode(sum % 10);
    			
    			if(head == null && tail == null) { 
    				head = tail = tmp;
    			}else { 
    				tail.next = tmp;
    				tail = tail.next;
    			}
    			
    			if(l1 != null) { 
    				l1 = l1.next;
    			}
    			if(l2 != null) { 
    				l2 = l2.next;
    			}
    		}
    		
    		if(carry != 0) { 
    			tail.next = new ListNode(carry);
    			tail = tail.next;
    		}
    		
    		return head;
    	}
    	
    	//方法二：比方法一精简些
    	public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {  
    		int carry = 0;
    		ListNode head = null, tail = null;
    		while(l1 != null || l2 != null || carry != 0) { 
    			
    			int a = l1 != null ? l1.val : 0 ;
    			int b = l2 != null ? l2.val : 0;
    			
    			int sum = a + b + carry;
    			carry = sum / 10;
    			
    			ListNode tmp = new ListNode(sum % 10);
    			
    			if(head == null && tail == null) { 
    				head = tail = tmp;
    			}else { 
    				tail.next = tmp;
    				tail = tail.next;
    			}
    			
    			if(l1 != null) l1 = l1.next;
    			if(l2 != null) l2 = l2.next;
    		}
    		
    		return head;
    	}
    	
    
    }

## Test ##

import static org.junit.Assert.*;
    import static com.lun.util.SinglyLinkedList.*;
    
    import org.junit.Test;
    
    import com.lun.util.SinglyLinkedList.ListNode;
    
    
    public class AddTwoNumbersTest { 
    
    	@Test
    	public void testTransform() { 
    		assertTrue(areTwoListEqual(ints2List(1), transform(1)));
    		assertTrue(areTwoListEqual(ints2List(9, 8, 7, 6, 9, 8, 7, 6), transform(67896789)));
    		assertTrue(areTwoListEqual(ints2List(3, 2, 1), transform(123)));
    	}
    	
    	@Test
    	public void testAddTwoNumbers() { 
    		AddTwoNumbers an = new AddTwoNumbers();
    
    		assertTrue(areTwoListEqual(ints2List(2, 2, 2), an.addTwoNumbers1(transform(111), transform(111))));
    		assertTrue(areTwoListEqual(ints2List(7, 0, 8), an.addTwoNumbers1(transform(342), transform(465))));
    		assertTrue(areTwoListEqual(ints2List(0, 0, 0, 1), an.addTwoNumbers1(transform(990), transform(10))));
    
    		assertTrue(areTwoListEqual(ints2List(2, 2, 2), an.addTwoNumbers2(transform(111), transform(111))));
    		assertTrue(areTwoListEqual(ints2List(7, 0, 8), an.addTwoNumbers2(transform(342), transform(465))));
    		assertTrue(areTwoListEqual(ints2List(0, 0, 0, 1), an.addTwoNumbers2(transform(990), transform(10))));
    		
    	}
    	
    	//将整数转换成链表
    	private ListNode transform(int from) { 
    		
    		//个位
    		int digit = from % 10;
    		ListNode tail = new ListNode(digit);
    		ListNode head = tail;
    		from = (from - digit) / 10;
    		
    		while(from > 0) { 
    			digit = from % 10;
    			tail.next = new ListNode(digit);
    			tail = tail.next;
    			from = (from - digit) / 10;
    		}
    		
    		return head;
    	}
    }

[https_leetcode.com_problems_add-two-numbers]: https://leetcode.com/problems/add-two-numbers/