当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

LeetCode[链表] - #2 Add Two Numbers

发表于: 2015-07-21   作者:Cwind   来源:转载   浏览:
摘要: 原题链接:#2 Add Two Numbers   要求: 给定两个以链表表示的非负整数,链表中的每个节点保存整数中的一位,以倒序排列(例如,321表示为1->2->3)。把这两个数字相加,作为一个链表返回。   输入:(2->4->3) + (5->6->4) 输出:7->0->8   难度:中等 &

原题链接:#2 Add Two Numbers

 

要求:

给定两个以链表表示的非负整数,链表中的每个节点保存整数中的一位,以倒序排列(例如,321表示为1->2->3)。把这两个数字相加,作为一个链表返回。

 

输入:(2->4->3) + (5->6->4)

输出:7->0->8

 

难度:中等

 

分析:

本题思路比较直接,以两个指针分别遍历两个链表。值得注意的是需要进位的情况的处理。当两个指针指向的节点的值相加大于10时,设置进位标记,结果节点的值设为其和除以10取余。当一个链表遍历完成,则关注另一个链表剩余部分的进位情况即可。

 

解决方案:

Java - 504 ms

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }else if(l2==null){
            return l1;
        }
        ListNode result;
        ListNode cur;
        int curSum = l1.val + l2.val;
        boolean plusOne = false;
        if(curSum>9){
            curSum = curSum % 10;
            plusOne = true;
        }
        cur = new ListNode(curSum);
        result = cur;
        while (l1.next!=null&&l2.next!=null){
            l1 = l1.next;
            l2 = l2.next;

            if(plusOne){
                curSum = l1.val + l2.val + 1;
            }else {
                curSum = l1.val + l2.val;
            }
            if(curSum>9){
                curSum = curSum % 10;
                plusOne = true;
            }else {
                plusOne = false;
            }

            cur.next = new ListNode(curSum);
            cur = cur.next;
        }
        if(l1.next==null&&l2.next==null) {
            if(plusOne){
               cur.next = new ListNode(1);
            }
            return result;
        }else if(l1.next==null){
            while (l2.next!=null){
                l2 = l2.next;
                if(plusOne){
                    curSum = l2.val + 1;
                    if(curSum>9){
                        curSum = curSum %10;
                        plusOne = true;
                    }else {
                        plusOne = false;
                    }
                }else {
                    curSum = l2.val;
                    plusOne = false;
                }
                cur.next = new ListNode(curSum);
                cur = cur.next;
            }
        }else if(l2.next==null){
            while (l1.next!=null){
                l1 = l1.next;
                if(plusOne){
                    curSum = l1.val + 1;
                    if(curSum>9){
                        curSum = curSum%10;
                        plusOne = true;
                    }else {
                        plusOne = false;
                    }
                }else {
                    curSum = l1.val;
                    plusOne = false;
                }
                cur.next = new ListNode(curSum);
                cur = cur.next;
            }
        }
        if(plusOne){
            cur.next = new ListNode(1);
        }
        return result;
    }

 简单测试程序

LeetCode[链表] - #2 Add Two Numbers

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号