聲明： 本總結(jié)僅為個(gè)人學(xué)習(xí)總結(jié)，以防止遺忘而作杈帐，不得轉(zhuǎn)載和商用。
題目：給定兩個(gè)鏈表,分別表示非負(fù)整數(shù).它們的數(shù)字逆序存儲(chǔ)在鏈表中,且每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)數(shù)字,計(jì)算兩個(gè)數(shù)的和,并且返回和的鏈表頭指針
如： 2->4->3、5->6->4,輸出: 7->0->8
分析：因?yàn)閮蓚€(gè)數(shù)都是逆序存儲(chǔ)，正好可以從頭向后依次相加荤傲，完成“兩個(gè)數(shù)的豎式計(jì)算”
Java版本的實(shí)現(xiàn)如下：
1、鏈表的構(gòu)建

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;//新結(jié)點(diǎn)插入到pTail后面
        Node p1 = node1.next;
        Node p2 = node2.next;
        Node pCur;
        int carry = 0;//進(jìn)位
        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;//新結(jié)點(diǎn)鏈接到pTail的后面
            pTail = pCur;
            
            p1 = p1.next;//處理下一位
            p2 = p2.next;
        }
        //處理較長(zhǎng)的鏈
        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、鏈表構(gòu)建及測(cè)試

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俊嗽、輸出結(jié)果如下：

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->