LeetCode2 两数相加(链表)
程序员文章站
2022-04-04 09:03:14
...
描述 :
C++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
}
};
解题思路
1)获取链表L1的长度、L2的长度
2)比较两者的长度,不一致少的部分要在链表的末尾添加0补齐
3)创建新的链表记录结果
4)逐个移位链表结点,相加,并记录进位
5)返回最终链表的结果
C++实现:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int len1=1;//记录l1的长度
int len2=1;//记录l2的长度
ListNode* p=l1;//l1的移动指针p
ListNode* q=l2;//l2的移动指针q
//获取链表长度
while(p->next!=NULL)//获取l1的长度
{
len1++;
p=p->next;
}
while(q->next!=NULL)//获取l2的长度
{
len2++;
q=q->next;
}
//对齐
if(len1>len2)//l1较长,在l2末尾补零
{
for(int i=1;i<=len1-len2;i++)
{
q->next=new ListNode(0);
q=q->next;
}
}
else//l2较长,在l1末尾补零
{
for(int i=1;i<=len2-len1;i++)
{
p->next=new ListNode(0);
p=p->next;
}
}
//求和
p=l1;//回到链表的初始位置
q=l2;//回到链表的初始位置
bool count=false;//记录进位
ListNode* l3=new ListNode(-1);//存放结果的链表
ListNode* w=l3;//l3的移动指针 w
int i=0;//记录相加结果
while(p!=NULL&&q!=NULL)
{
i=count+p->val+q->val;
w->next=new ListNode(i%10);
count=i>=10?true:false;
w=w->next;
p=p->next;
q=q->next;
}
//特殊情况考虑
if(count)//若最后还有进位
{
w->next=new ListNode(1);
w=w->next;
}
return l3->next;
}
};
时间复杂度O(n)
注意:
Python3实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
#创建新的链表
prenode = ListNode(0)
lastnode = prenode#移位链表lastnode
val = 0#进位
while val or l1 or l2:
val, cur = divmod(val + (l1.val if l1 else 0) + (l2.val if l2 else 0), 10)#函数返回val 进位 cur 取余值
lastnode.next = ListNode(cur)
lastnode = lastnode.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return prenode.next
python divmod() 函数把除数和余数运算结果结合起来,返回一个包含商和余数的元组(a // b, a % b)。
参考:
上一篇: leetCode 322. 零钱兑换
下一篇: 322. 零钱兑换(Java)