Leetcode:Add Two Numbers分析和实现

Add Two Numbers这个问题的意思是,提供两条链表,每条链表表示一个十进制整数,其每一位对应链表的一个结点。比如345表示为链表5->4->3。而我们需要做的就是将两条链表代表的整数加起来,并创建一个新的链表并返回,新链表代表加总值。


这个问题与算法无关,其主要是操作链表这一数据结构,以及两个大数的加法。由于没有规定链表的长度,这意味着链表代表的整数可以任意大,这样就不能先利用链表计算出对应的整数值,之后利用加总值重新生成链表。我们必须手动处理两个大数的加法。

要谨慎两个个位数的加总结果是有可能需要进位的,即7+8实际上等于10x1+5,其中1应该进位到下一个结点,而5当作这个当前结点的值。

addTwoNumbers(Node n1, Node n2)

  res = Node{val = (n1.val + n2.val) % 10, next = null}

  tail = res

  adv = (n1.val + n2.val) / 10

  n1 = n1.next

  n2 = n2.next

  while n1 != null && n2 != null then

    sum = n1.val + n2.val + adv

    tail.next = Node{val = sum % 10, next = null}

    tail = tail.next

    adv = sum / 10

    n1 = n1.next

    n2 = n2.next

  Node notEndedNode = (n1 == null ? n2 : n1)

  while notEndedNode != null then

    sum = notEndedNode .val + adv

    tail.next = Node{val = sum % 10, next = null}

    tail = tail.next

    adv = sum / 10

    notEndedNode = notEndedNode.next

  while adv != 0 then

    tail.next = Node{val = adv % 10, next = null}

    tail = tail.next

    adv = adv / 10

  return res


下面直接给出java的实现代码

package cn.dalt.leetcode;

/**
 * Created by Administrator on 2017/6/4.
 */
public class AddTwoNumbers {

    public static void main(String[] args)
    {
        System.out.println(new AddTwoNumbers().addTwoNumbers(new ListNode(342), new ListNode(465)));
    }

    static class ListNode {
        ListNode(int x)
        {
            val = x % 10;
            int adv = x / 10;
            if(adv != 0)
            {
                next = new ListNode(adv);
            }
        }

        @Override
        public String toString() {
            return "" + val + (next != null ? "->" + next.toString() : "");
        }

        int val;
        ListNode next;
    }

    static class NodeList{
        ListNode tail;
        ListNode root;
        int advance = 0;
        public NodeList(int x)
        {
            root = new ListNode(x % 10);
            tail = root;
            advance = x / 10;
        }
        public void append(int x)
        {
            x += advance;
            ListNode temp = new ListNode(x % 10);
            advance = x / 10;

            tail.next = temp;
            tail = temp;
        }
        public ListNode getResult()
        {
            while(advance != 0)
            {
                append(0);
            }
            return root;
        }

        @Override
        public String toString() {
            return root.toString();
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        NodeList list = new NodeList(l1.val + l2.val);
        l1 = l1.next;
        l2 = l2.next;

        while(l1 != null && l2 != null)
        {
            list.append(l1.val + l2.val);
            l1 = l1.next;
            l2 = l2.next;
        }
        while(l1 != null)
        {
            list.append(l1.val);
            l1 = l1.next;
        }
        while(l2 != null)
        {
            list.append(l2.val);
            l2 = l2.next;
        }
        return list.getResult();
    }
}
上一篇:Jquery属性练习


下一篇:hdu 2191悼念512汶川大地震遇难同胞——珍惜现在,感恩生活(多重背包)