LeetCode-2. 两数相加 Java & Go

给出两个非空的链表来表示两个非负整数。其中，他们各自的位数是按照逆序的方式存储，并且每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表表示他们的和。

你可以假设处理数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：(7 -> 0 -> 8)
原因：342 + 465 = 807

解答

2.两数相加.png

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
// 循环实现
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(0);
    ListNode cur = head;
    int carry = 0;
    while (l1 != null || l2 != null) {
        int a = 0, b = 0;
        if (l1 != null) {
            a = l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            b = l2.val;
            l2 = l2.next;
        }
        int val = (a + b + carry) % 10;
        carry = (a + b + carry) / 10;
        cur.next = new ListNode(val);
        cur = cur.next;
    }
    if (carry > 0) {
        cur.next = new ListNode(carry);
    }
    return head.next;
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
// 递归实现
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    return add(l1, l2,0);
}

private ListNode add(ListNode l1, ListNode l2,int carry){
    if (l1 == null && l2 == null) {
        if (carry > 0){
            return new ListNode(carry);
        }
        return null;
    }

    int v1 = 0, v2 = 0;

    if (l1 != null) {
        v1 = l1.val;
        l1 = l1.next;
    }
    if (l2 != null) {
        v2 = l2.val;
        l2 = l2.next;
    }

    int value = (v1 + v2 + carry) % 10;
    carry = (v1 + v2 + carry) / 10;

    ListNode result = new ListNode(value);
    result.next = add(l1, l2, carry);
    return result;
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 循环实现
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // 创建一个 dummy head
    var head = &ListNode{}
    cur := head
    carry := 0

    for l1 != nil || l2 != nil {
        a, b := 0, 0
        if l1 != nil {
            a = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            b = l2.Val
            l2 = l2.Next
        }
        val := (a + b + carry) % 10
        carry = (a + b + carry) / 10

        cur.Next = &ListNode{Val: val}
        cur = cur.Next
    }
    
    if carry > 0 {
        cur.Next = &ListNode{Val:carry}
    }
    return head.Next
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 递归实现
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return add(l1, l2, 0)
}

func add(l1 *ListNode, l2 *ListNode, carry int) *ListNode {
    // 递归停止条件
    if l1 == nil && l2 == nil {
        if carry > 0 {
            return &ListNode{Val: carry}
        }
        return nil
    }

    a, b := 0, 0
    

    if l1 != nil {
        a = l1.Val
        l1 = l1.Next
    }
    if l2 != nil {
        b = l2.Val
        l2 = l2.Next
    }

    nodeVal := (a + b + carry) % 10
    carry = (a + b + carry) / 10

    result := &ListNode{Val: nodeVal,}
    result.Next = add(l1, l2, carry)

    return result
}

上一题：1. 两数之和 Java & Go
下一题：3. 无重复字符的最长子串 Java & Go

最后编辑于：2019.05.13 16:33:05