链表的相加

声明： 本总结仅为个人学习总结，以防止遗忘而作，不得转载和商用。
题目：给定两个链表,分别表示非负整数.它们的数字逆序存储在链表中,且每个结点只存储一个数字,计算两个数的和,并且返回和的链表头指针
如： 2->4->3、5->6->4,输出: 7->0->8
分析：因为两个数都是逆序存储，正好可以从头向后依次相加，完成“两个数的竖式计算”
Java版本的实现如下：
1、链表的构建

public static class Node {
        public int value;
        public Node next;
        public Node(int data) {
            this.value = data;
        }
    }

2、链表的打印

public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + "->");
            node = node.next;
        }
        System.out.println();
    }

3、链表的相加

public static Node add(Node node1, Node node2){
        Node sumNode = new Node(0);
        Node pTail = sumNode;//新结点插入到pTail后面
        Node p1 = node1.next;
        Node p2 = node2.next;
        Node pCur;
        int carry = 0;//进位
        int value;
        while(p1 != null && p2 != null){
            value = p1.value + p2.value + carry;
            carry = value / 10;
            value %= 10;
            pCur = new Node(value);
            pTail.next = pCur;//新结点链接到pTail的后面
            pTail = pCur;
            
            p1 = p1.next;//处理下一位
            p2 = p2.next;
        }
        //处理较长的链
        Node pNode = p1 != null ? p1 : p2;
        while(pNode != null){
            value = pNode.value + carry;
            carry = value / 10;
            value %= 10;
            pCur = new Node(value);
            pTail.next = pCur;
            pTail = pCur;
            pNode = pNode.next;
        }
        if (carry != 0) {
            pTail.next = new Node(carry);
        }
        return sumNode;
    }

4、链表构建及测试

public static void main(String[] args) {
        Node node1 = new Node(0);
        for(int i=0;i<6;i++){
            Node node = new Node(new Random().nextInt(10));
            node.next = node1.next;
            node1.next = node;
        }

        printLinkedList(node1);
        
        Node node2 = new Node(0);
        for(int i=0;i<9;i++){
            Node node = new Node(new Random().nextInt(10));
            node.next = node2.next;
            node2.next = node;
        }
        printLinkedList(node2);
        
        Node sum = add(node1, node2);
        printLinkedList(sum);
    }

5、输出结果如下：

Linked List: 0->6->1->6->9->3->4->
Linked List: 0->7->9->2->3->3->2->4->3->4->
Linked List: 0->3->1->9->2->7->6->4->3->4->