LeetCode[链表] - #2 Add Two Numbers 博客分类： LeetCode LeetCodeJavaAlgorithm题解LinkedList

原题链接：#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;
    }

 简单测试程序