你的位置:首页 > Java教程

[Java教程]No.002:Add Two Numbers


问题:

You are given two linked lists representing two non-negative numbers.
The digits are stored in reverse order and each of their nodes contain a single digit.
Add the two numbers and return it as a linked list.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

官方难度:

Medium

翻译:

现有2个链表结构,存储非0的数字,每个节点的数字都是个位数的而且倒着排序,把这2个链表的数字相加并倒序输出。

例子:

链表一:2->4->3

链表二:5->6->4

输出:7->0->8

思路:

1.Java中的链表结构,就是LinkedList。

2.Java中的集合迭代器ListIterator,拥有自末尾向前遍历的特性,在这里可以运用。

解题中可能遇到的困难:

1.创建ListIterator的时候,指针的位置需要指向链表的末尾。

解题代码:

 1   private static List<Integer> method(List<Integer> list1, List<Integer> list2) { 2     int sum1 = 0; 3     int sum2 = 0; 4     int size1 = list1.size(); 5     int size2 = list2.size(); 6     // 声明2个ListIterator,可以逆向迭代,指针位置先给到最后一位 7     ListIterator<Integer> iter1 = list1.listIterator(size1); 8     ListIterator<Integer> iter2 = list2.listIterator(size2); 9     // 逆序遍历+累加10     while (iter1.hasPrevious()) {11       sum1 += iter1.previous() * Math.pow(10, --size1);12     }13     while (iter2.hasPrevious()) {14       sum2 += iter2.previous() * Math.pow(10, --size2);15     }16     int sum = sum1 + sum2;17     List<Integer> resultList = new LinkedList<>();18     while (sum > 0) {19       // 取末尾20       resultList.add(sum % 10);21       // 去末尾22       sum /= 10;23     }24     return resultList;25   }

View Code

测试代码地址:

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/medium/Q002.java

LeetCode题目地址:

https://leetcode.com/problems/add-two-numbers/

PS:如有不正确或提高效率的方法,欢迎留言,谢谢!