首页 > 代码库 > [LeetCode#2]Add Two Numbers
[LeetCode#2]Add Two Numbers
The question:
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Analysis:
This question is simple,
digit = (l1_current.value + l2_current.value + carry) % 10;
carry = (l1_current.value + l2_current.value + carry) % 10;
Corner case:
Apparently, we would do the above computation in the while loop: while (l1_current ! = null || l2_current).
When we exit from the loop, there could be a situation that carry is 1, while all nodes in list 1 and list 2 has already been scanned.
we need to tackle this situation by adding following lines:
if (carry == 1) { //take care, there might be a additional carry in the last digit newNode = new ListNode(1); temp.next = newNode; temp = temp.next; }
My solution:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode lr = new ListNode(0); ListNode temp = lr; //used to remember the current scan position, note: this is dummpy head for keeping loop invariant! ListNode l1_current = l1; //not dumy head ListNode l2_current = l2; ListNode newNode = null; int carry = 0; //set the initial carry into zero while (l1_current != null || l2_current != null) { if (l1_current == null && l2_current != null) { newNode = new ListNode((l2_current.val + carry) % 10); carry = (l2_current.val + carry) / 10; //there is no carry for next digit(next upper digit) l2_current = l2_current.next; //continue; } if (l2_current == null && l1_current != null) { newNode = new ListNode((l1_current.val + carry) % 10); carry = (l1_current.val + carry) / 10; l1_current = l1_current.next; //continue; } if (l1_current != null && l2_current != null) { newNode = new ListNode((l1_current.val + l2_current.val + carry) % 10); carry = (l1_current.val + l2_current.val + carry) / 10; l1_current = l1_current.next; l2_current = l2_current.next; //continue the continue would jump over the temp~~~~ careful! } temp.next = newNode; //the head of the result list is recored in lr temp = temp.next; //move the scanner to the next position } if (carry == 1) { //take care, there might be a additional carry in the last digit newNode = new ListNode(1); temp.next = newNode; temp = temp.next; } return lr.next; }}
[LeetCode#2]Add Two Numbers