描述
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。给定两个这种链表,请生成代表两个整数相加值的结果链表。
示例1
1 2
| 输入: [9,3,7],[6,3] 返回: {1,0,0,0}
|
示例2
题解
链表反转
- 两个链表反转
- 遍历两个链表,将相加结果接入结果链表
- 反转结果链表
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
| package main
type ListNode struct{ Val int Next *ListNode }
func addInList( head1 *ListNode , head2 *ListNode ) *ListNode { rl1, rl2 := reverse(head1), reverse(head2) newHead := &ListNode{} cur := newHead plus := 0
for rl1 != nil || rl2 != nil { node := &ListNode{Val: plus} if rl1 != nil { node.Val += rl1.Val rl1 = rl1.Next } if rl2 != nil { node.Val += rl2.Val rl2 = rl2.Next }
plus = node.Val / 10 node.Val = node.Val % 10 cur.Next = node cur = cur.Next }
if plus > 0 { cur.Next = &ListNode{Val: plus} }
return reverse(newHead.Next) }
func reverse(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head }
var pre *ListNode
for head != nil { temp := head.Next head.Next = pre pre = head head = temp }
return pre }
|