单链表加法

题目出处

• 面试实际遇到过

1 题目描述

单链表表示一个大整数，头结点表示高位，每位都是个位数

计算大整数+1

2 解题思路

反转，加数，再反转

public class Test {
    public static void main(String[] args) {
        Node node = new Node(9);
        node.next = new Node(9);
        node.next.next = new Node(9);
        node.next.next.next = new Node(9);
        Node result = caculateInteger(node);
        while(null != result){
            System.out.println(result.value);
            result = result.next;
        }
    }

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

    private static Node caculateInteger(Node head){
        head = reverseLinkedList(head);
        caculateIntegerList(head, 1);
        head = reverseLinkedList(head);
        return head;
    }

    private static void caculateIntegerList(Node head, int addValue){
        while(null != head){
            head.value = head.value + addValue;
            if(head.value > 9){
                addValue = head.value / 10;
                head.value = head.value % 10;
                if(null == head.next){
                    head.next = new Node(0);
                }
                head = head.next;
            }else{
                break;
            }
        }
    }

    private static Node reverseLinkedList(Node head){
        if(null == head || null == head.next){
            return head;
        }

        Node first = head;
        Node second = head.next;
        while(null != second){
            Node temp = second.next;
            second.next = first;
            first = second;
            second = temp;
        }
        head.next = null;
        return first;
    }
}