欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-15 08:09:11
...

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

 简单测试程序