Add Two Numbers

题目.png

解决思路

可以将两个链表长度统计出来，将短的链表最高位看作0，递归处理即可求得结果。

example：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    countA := 0
    countB := 0
    for cur := l1; cur != nil; cur = cur.Next {
        countA ++
    }
    for cur := l2; cur != nil; cur = cur.Next {
        countB ++
    }
    sub := 0
    max := 0
    var long *ListNode
    var short *ListNode
    if countA > countB {
        sub = countA - countB
        long = l1
        short = l2
        max = countA
    }else {
        sub = countB - countA
        long = l2
        short = l1
        max = countB
    }
    
    next, flag := add(short, long, max, sub) 
    if flag {
        return &ListNode{
            Val : 1,
            Next: next,
        }
    }else {
        return next
    }
}

func add(short *ListNode, long *ListNode, count int, sub int) (*ListNode, bool){
    if count == 0 {
        return nil, false
    }
    a := 0
    b := 0
    c := 0
    flag := false
    var next *ListNode
    if sub != 0 {
        next, flag = add(short, long.Next, count-1, sub-1)
    }else {
        next, flag = add(short.Next, long.Next, count-1, 0)
        a = short.Val
    }
    b = long.Val
    if flag {
        c = 1
    }
    sum := a + b + c
    if sum >= 10 {
        return &ListNode{
            Val : sum - 10,
            Next: next, 
        }, true
    }else {
        return &ListNode{
            Val : sum,
            Next: next, 
        }, false 
    }
}

也可以将链表反转，从最低位开始计算。
反转链表：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    previous := head
    cur := previous.Next
    previous.Next = nil
    for cur != nil {
        temp := cur.Next
        cur.Next = previous
        previous = cur
        cur = temp 
    }
    return previous
}

链表是数字的逆序时，直接按位相加即可

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    head := &ListNode{}
    temp := head
    a := 0
    b := 0
    sum := 0
    add := false
    for ; ; {
        if l1 != nil {
            a = l1.Val
            l1 = l1.Next
            
        }else{
            a = 0
        }
        if l2 != nil {
            b = l2.Val
            l2 = l2.Next
        }else {
            b = 0
        }
        if add {
            sum = a + b + 1
        }else {
            sum = a + b
        }
        if sum >= 10 {
            temp.Val = sum - 10
            add = true
        }else{
            temp.Val = sum
            add = false
        }
        
        if l1 != nil || l2 != nil || add {
            temp.Next = &ListNode{}
            temp = temp.Next 
        }else {
            break
        }
    }
    return head
}