445.两数相加II

2020/4/14 10:46 上午 posted in  链表 leetcode
Tags:  #链表

问题

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。
示例:

输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 8 -> 0 -> 7

解法

不考虑进阶的话,整体比较简单,首先翻转两个链表,然后从头加到尾就是结果,需要注意两点

  1. 两个链表长度可能不一致,需要在低位加完后补充高位。
  2. 需要考虑进位问题,比如9+3=12,那么本位上需要存3,然后在下一位中进位(还有一个特殊情况,如,5+5=10,那么最终为1->0)

    代码

    /**
    * Definition for singly-linked list.
    * public class ListNode {
    * int val;
    * ListNode next;
    * ListNode(int x) { val = x; }
    * }
    */
    class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    //首先反转两个链表
    ListNode revertl1 = revert(l1);
    ListNode revertl2 = revert(l2);
    ListNode head = null;
    boolean carry = false;
    while(revertl1 != null && revertl2 !=null) {
    int num = revertl1.val + revertl2.val;
    if (carry){
    num += 1;
    }
    if (num > 9) {
    carry = true;
    num -=10;
    } else {
    carry = false;
    }
    ListNode cur = new ListNode(num);
    if (head != null) {
    cur.next = head;
    }
    head = cur;
    revertl1 = revertl1.next;
    revertl2 = revertl2.next;
    }
    while(revertl1 !=null) {
    int num = revertl1.val;
    if (carry) {
    num +=1;
    }
    if (num>9) {
    carry = true;
    num-=10;
    } else {
    carry = false;
    }
    ListNode cur = new ListNode(num);
    cur.next = head;
    head = cur;
    revertl1 = revertl1.next;
    }
    while(revertl2 !=null) {
    int num = revertl2.val;
    if (carry) {
    num +=1;
    }
    if (num>9) {
    carry = true;
    num-=10;
    } else {
    carry = false;
    }
    ListNode cur = new ListNode(num);
    cur.next = head;
    head = cur;
    revertl2 = revertl2.next;
    }
    if (carry) {
    ListNode cur = new ListNode(1);
    cur.next= head;
    head = cur;
    }
    return head;
    }
    private ListNode revert(ListNode node) {
    ListNode head = null;
    while(node != null) {
    ListNode cur = new ListNode(node.val);
    if (head !=null) {
    cur.next = head;
    }
    head = cur;
    node = node.next;
    }
    return head;
    }
    }