一、题意
给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字0之外,这两个数都不会以0开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
题目来源:leetcode-两数相加
二、分析
三、代码实现
main.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { res := &ListNode{} cur := res carry := 0 for l1 != nil && l2 != nil { sum := l1.Val + l2.Val + carry val := sum % 10 carry = sum / 10 lnode := &ListNode{Val: val} cur.Next = lnode cur = cur.Next l1 = l1.Next l2 = l2.Next } if carry == 0 { if l1 != nil { cur.Next = l1 } else { cur.Next = l2 } } else { for l1 != nil { sum := l1.Val + carry val := sum % 10 carry = sum / 10 node := &ListNode{Val: val} cur.Next = node cur = cur.Next l1 = l1.Next } for l2 != nil { sum := l2.Val + carry val := sum % 10 carry = sum / 10 node := &ListNode{Val: val} cur.Next = node cur = cur.Next l2 = l2.Next } for carry != 0 { val := carry % 10 carry = carry / 10 node := &ListNode{Val: val} cur.Next = node cur = cur.Next } } return res.Next }
|
四、测试代码
test.go
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
| package problem007
import ( "fmt" "testing"
"github.com/stretchr/testify/assert" )
func createList(vals []int) *ListNode { if len(vals) == 0 { return nil } res := &ListNode{ Val: vals[0], } cur := res for i := 1; i < len(vals); i++ { cur.Next = &ListNode{ Val: vals[i], } cur = cur.Next } return res }
func printList(l *ListNode) { for l != nil { val := l.Val l = l.Next if l == nil { fmt.Printf("%d", val) } else { fmt.Printf("%d --> ", val) } } }
func Test_addTwoNumbers(t *testing.T) { ast := assert.New(t) l1 := createList([]int{2, 4, 3}) l2 := createList([]int{5, 6, 4}) ans := createList([]int{7, 0, 8}) res := addTwoNumbers(l1, l2) ast.Equal(ans, res) fmt.Printf("输入:(") printList(l1) fmt.Printf(") + (") printList(l2) fmt.Println(")") fmt.Printf("输出:") printList(res) fmt.Println() }
=== RUN Test_addTwoNumbers 输入:(2 --> 4 --> 3) + (5 --> 6 --> 4) 输出:7 --> 0 --> 8 --- PASS: Test_addTwoNumbers (0.00s) PASS
Process finished with exit code 0
|
五、总结与思考
本题和合并两个排序的链表类似,在构造链表时,都是顺序遍历两个链表。两数之和每次都是将两个链表对应的结点的值域相加,合并链表则是每次取其中值较大或者较小者。
六、C++ 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
|
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { if(l1 == NULL && l2 == NULL) { return NULL; } else if(l1 == NULL && l2 != NULL) { return l2; } else if(l2 == NULL && l1 != NULL) { return l1; } int len1 = 1; int len2 = 1; ListNode* p = l1; ListNode* q = l2; while(p->next != NULL) { ++len1; p = p->next; } while(q->next != NULL) { ++len2; q = q->next; } if(len1 > len2) { for(int i = 1; i <= len1-len2; ++i) { q->next = new ListNode(0); q = q->next; } } if(len1 < len2) { for(int i = 1; i <= len2-len1; ++i) { p->next = new ListNode(0); p = p->next; } } p = l1; q = l2; bool carry = false; ListNode* res = new ListNode(-1); ListNode* cur = res; int sum = 0; while(p != NULL && q != NULL) { sum = p->val + q->val + carry; cur->next = new ListNode(sum%10); carry = sum >= 10 ? true : false; cur = cur->next; p = p->next; q = q->next; } if(carry != 0) { cur->next = new ListNode(1); cur = cur->next; } return res->next; } };
|
来做第一个留言的人吧!