本文在于解答LeetCode中的第二题，问题的描述可参见 两数相加
Golang的实现：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
result := &ListNode{}
nodes := []*ListNode{}
var carry = 0
for {
node, c := add(l1, l2, carry)
carry = c
if node != nil {
nodes = append(nodes, node)
if l1 != nil && l1.Next != nil {
l1 = l1.Next
} else {
l1 = nil
}
if l2 != nil && l2.Next != nil {
l2 = l2.Next
} else {
l2 = nil
}
if carry > 0 && (l1 == nil && l2 == nil) {
nodes = append(nodes, &ListNode{Val:carry})
}
} else {
break
}
}
for i, n := range nodes{
if i == 0 {
result = n
}
if i + 1 < len(nodes) {
n.Next = nodes[i + 1]
}
}
return result
}
func add (n1 *ListNode, n2 *ListNode, carry int) (*ListNode, int) {
node := &ListNode{}
if (n1 == nil && n2 == nil) {
return nil, 0
}
if n1 == nil {
n1 = &ListNode{Val : 0}
}
if n2 == nil {
n2 = &ListNode{Val : 0}
}
sum := n1.Val + n2.Val + carry
carry = 0
if sum > 9 {
carry = 1
sum = sum - 10
}
node.Val = sum
return node, carry
}
下面提供Scheme版本的实现【(1 0) + (9 1 2) = (0 2 2)】，为了简单起见，与题目要求稍有不同，这里采用list，而不是题目要求的链表，但实际上应是一样的。比较之下可以看出，相对而言，Scheme语言的实现更加简短优雅，得益于其强大的表达能力
(letrec (
[Polishing
(lambda (l num)
(if (eq? num 0) l (Polishing (append l '(0)) (- num 1)))
)
]
[Align
(lambda (l1 l2)
(let ([len1 (length l1)] [len2 (length l2)])
(if [eq? len1 len2] [list l1 l2]
[if (> len1 len2) (list l1 (Polishing l2 (- len1 len2)))
(list (Polishing l1 (- len2 len1)) l2)]))
)
]
[Add
(lambda (l1 l2)
(let ([ l (Align l1 l2)])
(Carry (map (lambda (x y) (+ x y)) (car l) (cadr l)) 0)
)
)
]
[Carry
(lambda (l c)
(if (null? l)
(if [eq? c 0] '() [cons c l])
(cons (mod ( + (car l) c ) 10) (Carry (cdr l) (quotient ( + (car l) c) 10)))
)
)
])
(Add '(1 0) '(9 1 2)))
Golang版本和Scheme版本的实现思路不相同，简要描述一下后者：
- (1 0) + (9 1 2), 先进行补位：
- (1 0 0) + (9 1 2), 按顺序相加，得：
- (10 1 2), 再计算进位：
- (0 2 2)
