cc150 Chapter 2 | Linked Lists 2.5 add two integer LinkedList, return LinkedList as a sum

2.5 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. EXAMPLE Input: (3 -> 1 -> 5) + (5 -> 9 -> 2) Output: 8 -> 0 -> 8

给两个整型链表，每个节点包含一个位数，这些位数是反向存放的，也就是个位数在链表首部，编写程序，对这两个整数求和，并用链表形式返回结果。

进阶：

假设这些位数是正向存放的，请再做一遍。

1.自己的思路是：取每个list的第一个，相加（随时取余，相除），放入新建一个列表的最后一个。

 1 public class newAdd5 {
 2     public static LinkedList<Integer> sum1(LinkedList<Integer> l1,
 3             LinkedList<Integer> l2) {
 4         LinkedList<Integer> l3 = new LinkedList<Integer>();
 5         if (l1.isEmpty())
 6             return l2;
 7         if (l2.isEmpty())
 8             return l1;
 9         int carry = 0;
10         while (!l1.isEmpty() && !l2.isEmpty()) {
11             int sum = 0;
12             sum = (l1.peek() + l2.peek() + carry) % 10;
13             carry = (l1.poll() + l2.poll() + carry) / 10;
14             l3.addFirst(sum);
15         }
16         while (!l1.isEmpty() && l2.isEmpty()) {
17             int sum = 0;
18             sum = (l1.peek() + carry) % 10;
19             carry = (l1.poll() + carry) / 10;
20             l3.addFirst(sum);
21         }
22         while (!l2.isEmpty() && l1.isEmpty()) {
23             int sum = 0;
24             sum = (l2.peek() + carry) % 10;
25             carry = (l2.poll() + carry) / 10;
26             l3.addFirst(sum);
27         }
28         return l3;
29 
30     }
31 
32     // follow up
33     public static LinkedList<Integer> sum2(LinkedList<Integer> l1,
34             LinkedList<Integer> l2) {
35         java.util.Collections.reverse(l1);
36         java.util.Collections.reverse(l2);
37         LinkedList<Integer> l3 = new LinkedList<Integer>();
38         if (l1.isEmpty())
39             return l2;
40         if (l2.isEmpty())
41             return l1;
42         int carry = 0;
43         while (!l1.isEmpty() && !l2.isEmpty()) {
44             int sum = 0;
45             sum = (l1.peek() + l2.peek() + carry) % 10;
46             carry = (l1.poll() + l2.poll() + carry) / 10;
47             l3.addFirst(sum);
48         }
49         while (!l1.isEmpty() && l2.isEmpty()) {
50             int sum = 0;
51             sum = (l1.peek() + carry) % 10;
52             carry = (l1.poll() + carry) / 10;
53             l3.addFirst(sum);
54         }
55         while (!l2.isEmpty() && l1.isEmpty()) {
56             int sum = 0;
57             sum = (l2.peek() + carry) % 10;
58             carry = (l2.poll() + carry) / 10;
59             l3.addFirst(sum);
60         }
61         return l3;
62 
63     }
64 
65     public static void main(String[] args) {
66         Random rd = new Random();
67         LinkedList<Integer> list1 = new LinkedList<Integer>();
68         LinkedList<Integer> list2 = new LinkedList<Integer>();
69         int n1 = rd.nextInt(5);
70         for (int i = 0; i < n1; i++) {
71             list1.add(rd.nextInt(10));
72         }
73         int n2 = rd.nextInt(6);
74         for (int i = 0; i < n2; i++) {
75             list2.add(rd.nextInt(10));
76         }
77         System.out.println(list1.toString());
78         System.out.println(list2.toString());
79         System.out.println("After Adding: ");
80         System.out.println(sum1(list1, list2).toString());
81         LinkedList<Integer> list3 = new LinkedList<Integer>();
82         LinkedList<Integer> list4 = new LinkedList<Integer>();
83         for (int i = 0; i < n1; i++) {
84             list3.add(rd.nextInt(10));
85         }
86         for (int i = 0; i < n2; i++) {
87             list4.add(rd.nextInt(10));
88         }
89         System.out.println("Follow Up: ");
90         System.out.println(list3.toString());
91         System.out.println(list4.toString());
92         System.out.println(sum2(list3, list4).toString());
93     }
94 }

然后在网上看的方法更简洁：

public class Sum5 {
    public static void main(String[] args) {
        Random rd = new Random();
        LinkedList<Integer> list1 = new LinkedList<Integer>();
        LinkedList<Integer> list2 = new LinkedList<Integer>();
        int n1 = rd.nextInt(5);
        for (int i = 0; i < n1; i++) {
            list1.add(rd.nextInt(10));
        }
        int n2 = rd.nextInt(6);
        for (int i = 0; i < n2; i++) {
            list2.add(rd.nextInt(10));
        }
        System.out.println(list1.toString());
        System.out.println(list2.toString());
        System.out.println("After Adding: ");
        System.out.println(addReverse(list1, list2).toString());
        LinkedList<Integer> list3 = new LinkedList<Integer>();
        LinkedList<Integer> list4 = new LinkedList<Integer>();
        for (int i = 0; i < n1; i++) {
            list3.add(rd.nextInt(10));
        }
        for (int i = 0; i < n2; i++) {
            list4.add(rd.nextInt(10));
        }
        System.out.println("Follow Up: ");
        System.out.println(list3.toString());
        System.out.println(list4.toString());
        System.out.println(addForward(list3, list4).toString());
    }

    private static LinkedList<Integer> addReverse(LinkedList<Integer> list1,
            LinkedList<Integer> list2) {
        LinkedList<Integer> list3 = new LinkedList<Integer>();
        int sum = 0;
        while (!list1.isEmpty() || !list2.isEmpty() || sum != 0) {
            int tempsum = sum;
            if (!list1.isEmpty()) {
                tempsum += list1.poll();
            }
            if (!list2.isEmpty()) {
                tempsum += list2.poll();
            }
            list3.addFirst(tempsum % 10);
            sum = tempsum / 10;
        }
        return list3;
    }

    private static LinkedList<Integer> addForward(LinkedList<Integer> list1,
            LinkedList<Integer> list2) {
        LinkedList<Integer> list3 = new LinkedList<Integer>();
        int sum = 0;
        java.util.Collections.reverse(list1);
        java.util.Collections.reverse(list2);
        while (!list1.isEmpty() || !list2.isEmpty() || sum != 0) {
            int tempsum = sum;
            if (!list1.isEmpty()) {
                tempsum += list1.poll();
            }
            if (!list2.isEmpty()) {
                tempsum += list2.poll();
            }
            list3.addFirst(tempsum % 10);
            sum = tempsum / 10;
        }
        return list3;
    }
}