目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
两个链表生成相加链表
访问量:1219
一、简介
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
题目来源:牛客
二、实现
思路:考虑进位问题,所以需要从链表,最后面节点,依次往前,相加。首先,我们想到的是链表逆转后相加即可,其次,我们也可以借助栈,先进后出来实现。
下面是基于链表翻转实现:
/** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ func addInList( head1 *ListNode , head2 *ListNode ) *ListNode { // write code here if head1 == nil { return head2 } if head2 == nil { return head1 } head1 = revertList(head1) head2 = revertList(head2) var ( newHead *ListNode flag int ) for head1 != nil || head2 != nil { curVal := flag flag = 0 if head1 != nil { curVal += head1.Val head1 = head1.Next } if head2 != nil { curVal += head2.Val head2 = head2.Next } if curVal >= 10 { curVal = curVal - 10 flag +=1 // 进位加1 } newHead = &ListNode{ Val: curVal, Next: newHead, } } // 这一步不能遗漏,进位可能还存在 if flag != 0 { newHead = &ListNode{ Val: flag, Next: newHead, } } return newHead } // 翻转链表 func revertList(head *ListNode) *ListNode { var newHead *ListNode for head != nil { nextNode := head.Next head.Next = newHead newHead = head head = nextNode } return newHead }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助