题目如下:
这道题个人觉得没涉及到什么算法, 就是考数据结构 -- 链表. 那首先来简单复习一下链表:
链表 (Linked list) 是一种线性表, 但是并不会按线性的顺序存储数据, 而是在每一个节点里存到下一个节点的指针 (Pointer). 由于不必须按顺序存储, 链表在插入的时候可以达到 O(1) 的复杂度, 比另一种线性表顺序表快得多, 但是查找一个节点或者访问特定编号的节点则需要 O(n)的时间, 而顺序表相应的时间复杂度分别是 O(logn)和 O(1).
使用 Java 定义链表:
- public static class ListNode{
- int data;
- ListNode next;
- ListNode(int x){
- data = x;
- }
- }
在这道题中, 由于位数按照逆序存储, 即链表的头结点就是个位, 然后一次是十位, 百位..., 所以可以直接从头结点开始相加, 只需要将进位保存下来加到下一位的和上即可. 感觉这道题没什么可说的, 自己做的时候就是对链表的操作不熟练, 所以重点还是在数据结构上.
Java 代码实现
- package Leetcode;
- import java.util.Random;
- public class TwoPlusBter {
- // TODO create a listNode class
- public static class ListNode{
- int data;
- ListNode next;
- ListNode(int x){
- data = x;
- }
- // FOR i can output the ListNode with a String
- public String toString(){
- String res = "";
- for(ListNode p = this;p != null;p = p.next){
- res += p.data + " ";
- }
- return res;
- }
- }
- public static ListNode Solution(ListNode l1,ListNode l2){
- ListNode res = new ListNode(0);
- ListNode cur = res;//cur 作为 res 的引用, 改变 cur 即改变 res
- for(int carry = 0;l1 != null || l2 != null || carry > 0;){
- int val1 = l1 != null ? l1.data:0;
- int val2 = l2 != null ? l2.data:0;
- l1 = l1 != null ? l1.next:null;
- l2 = l2 != null ? l2.next:null;
- int sum = val1 + val2 + carry;// 各位相加
- carry = sum / 10; //carry 作为进位: 0 or 1
- cur.next = new ListNode(sum % 10);
- cur = cur.next;
- //System.out.println("aaa");
- }
- res = res.next;
- //System.out.println("aaa");
- return res;
- }
- public static ListNode Random(){
- ListNode test = new ListNode(0);
- ListNode cur = test , del = null;
- Random rd = new Random();
- int n = rd.nextInt(9) + 1; // 生成 [0,9) 的随机数
- System.out.println("n="+n);
- for(int i = 0;i<n;i++){
- cur.data = rd.nextInt(10);
- cur.next = new ListNode(0);
- del = cur; // del 指向 cur 的前一个结点
- cur = cur.next;
- // 这样的话跳出循环时 cur 会出现一个多余的结点, 所以利用 del 将此结点删除
- }
- del.next = null;
- return test;
- }
- public static void main(String[] args){
- ListNode l1 = Random();
- System.out.println(l1.toString());
- ListNode l2 = Random();
- System.out.println(l2.toString());
- ListNode res = Solution(l1,l2);
- System.out.println(res.toString());
- }
- }
来源: http://blog.51cto.com/acevi/2106742