add-two-numbers

leetcode开篇~

问题描述：

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

首先要看懂题目，囧。第一次看，着实没有看懂。。

翻译一下：用两个链表表示两个非负整数。链表每个节点表示一个数字，按照数字倒序排列。比如123，用链表表示是3->2->1。求两个数字相加的和，并用链表表示。如342+465=807，用链表表示为7->0->8.

解答：

第一次写完使用的是递归的方式，结果显示超时。如下：

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        return addTwoNumbers(l1, l2, false);

    }

    private static ListNode addTwoNumbers(ListNode l1, ListNode l2, boolean putMore){

        if(l1 == null && l2 == null){

            return putMore ? new ListNode(1) : null;

        }else if(l1 == null){

            return putMore ? addTwoNumbers(l2, new ListNode(1), false) : l2;

        }else if(l2 == null){

            return putMore ? addTwoNumbers(l1, new ListNode(1), false) : l1;

        }

        int value = putMore ? (l1.val+l2.val+1) : (l1.val+l2.val);

        putMore = value >= 10 ? true : false;

        ListNode result = new ListNode(value%10);

        result.next = addTwoNumbers(l1.next, l2.next, putMore);

        return result;

    }

　然后查看了其他人的解答，改为非递归方式：

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);

        ListNode node = head;

        ListNode p1 = l1;

        ListNode p2 = l2;

        boolean putMore = false;

        while (p1 != null || p2 != null || putMore){

            int add1 = p1 == null ? 0 : p1.val;

            int add2 = p2 == null ? 0 : p2.val;

            int value = putMore ? (add1+add2+1) : (add1+add2);

            putMore = value >= 10 ? true : false;

            node.next = new ListNode(value%10);

            if(p1 != null) p1 = p1.next;

            if(p2 != null) p2 = p2.next;

            node = node.next;

        }

        return head.next;

    }

加上测试代码：

    private static ListNode initListNode(List<Integer> valueList){

        ListNode result = new ListNode(valueList.get(0));

        ListNode node = result;

        for(int i=1; i<valueList.size(); i++){

            node.next = new ListNode(valueList.get(i));

            node = node.next;

        }

        return result;

    }

    private static List<Integer> getResult(ListNode node){

        List<Integer> result = Lists.newArrayList();

        ListNode temp = node;

        while (temp != null){

            result.add(temp.val);

            temp = temp.next;

        }

        return result;

    }

    public static void main(String[] args) {

        ListNode l1 = initListNode(Lists.newArrayList(6));

        System.out.println("l1:" + JSON.toJSONString(getResult(l1)));

        ListNode l2 = initListNode(Lists.newArrayList(6,9));

        System.out.println("l2:" + JSON.toJSONString(getResult(l2)));

        ListNode node = addTwoNumbers(l1, l2);

        System.out.println("result:" + JSON.toJSONString(getResult(node)));

    }

总结：

递归方式解答问题，比较容易想到。有了递归解答，要试着改成非递归的形式，提高性能。

巴特西

add-two-numbers

问题描述：

解答：

最新文章

热门文章