【链表专题】字节真题：单链表相加
本问题对应课程链接：剑指offer刷题第七期
要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度
代码参考
// 注意，关于链表节点的定义（ListNode），我这里没有给出来哦
class SolutionAdd {
// 反转链表
public ListNode reverseList(ListNode node){
ListNode pre = null;
ListNode q= null;
while (node != null) {
q= node.next;
node.next = pre;
pre = node;
node = q;
}
return pre;
}
// 单链表相加
public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
// 虚拟头节点
ListNode listNode = new ListNode(0);
ListNode p = listNode;
// sum 用来存放进位
int sum = 0;
while (head1 != null || head2 != null || sum!=0) {
if (head1 != null) {
sum += head1.val;
head1 = head1.next;
}
if (head2 != null) {
sum += head2.val;
head2 = head2.next;
}
p.next = new ListNode(sum % 10);
sum = sum / 10;
p = p.next;
}
return listNode.next;
}
}
时间复杂度：O(n+m)
空间复杂度：O(1)
shuaidi
共以下 32 个回答
class Solution {
// 两数相加Ⅱ
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
先将两个链表翻转，然后相加，最后在翻转
反转+合并
打印结果
打印开始———————-》
1 -> 2 -> 3 -> 4
打印结束———————-》
打印开始———————-》
6 -> 7
打印结束———————-》
打印开始———————-》
1 -> 3 -> 0 -> 1
打印结束———————-》
提供下我写的工具类和ListNode的定义
// 注意，关于链表节点的定义（ListNode），我这里没有给出来哦
class SolutionAdd {
// 反转链表
public ListNode reverseList(ListNode node){
ListNode pre = null;
ListNode q= null;
while (node != null) {
q= node.next;
node.next = pre;
pre = node;
node = q;
}
return pre;
}
// 单链表相加
public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
// 虚拟头节点
ListNode listNode = new ListNode(0);
ListNode p = listNode;
// sum 用来存放进位
int sum = 0;
while (head1 != null || head2 != null || sum!=0) {
if (head1 != null) {
sum += head1.val;
head1 = head1.next;
}
}
时间复杂度O(m+n)
空间复杂度O(max(m+n))
sum这块的写法可以更简单一点，不需要carry。定义一个前置节点能省去很多判断！
时间复杂度O(max(m,n))
空间复杂度O(1)
时间复杂度:O(n)
空间复杂度：O(m+n)
“`c++
ListNode* filp(ListNode* head){
if(!head)return nullptr;
if(!(head->next))return head;
ListNode* res=filp(head->next);
head->next->next=head;
head->next=nullptr;
return res;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1=filp(l1);
l2=filp(l2);
ListNode* res=new ListNode(-1,nullptr);
ListNode* p=res;
int cur=0;
int pre=0;
while(l1||l2||pre){
if(!l1&&l2){
cur=(l2->val+pre)%10;
p->next=new ListNode(cur);
pre=(l2->val+pre)/10;
l2=l2->next;
}else if(!l2&&l1){
cur=(l1->val+pre)%10;
p->next=new ListNode(cur);
pre=(l1->val+pre)/10;
l1=l1->next;
}else if(!l1&&!l2){
cur=pre%10;
p->next=new ListNode(pre);
pre=pre/10;
}else{
cur=(l1->val+l2->val+pre)%10;
p->next=new ListNode(cur);
pre=(l1->val+l2->val+pre)/10;
l1=l1->next;
l2=l2->next;
}
p=p->next;
}
return filp(res->next);
}
“`
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *pHead=nullptr;
auto p1=l1,p1Cur=l1,p2=l2,p2Cur=l2;
while(p1!=nullptr&&p2!=nullptr)
{
p1=p1->next;
p2=p2->next;
}
};
执行时间超过6.9%的提交用户
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
““java
// 注意，关于链表节点的定义（ListNode），我这里没有给出来哦
class SolutionAdd {
// 反转链表
public ListNode reverseList(ListNode node){
ListNode pre = null;
ListNode q= null;
while (node != null) {
q= node.next;
node.next = pre;
pre = node;
node = q;
}
return pre;
}
// 单链表相加
public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
l1=reverseList(head1);
l2=reverseList(head2);
// 虚拟头节点
ListNode listNode = new ListNode(0);
ListNode p = listNode;
// sum 用来存放进位
int sum = 0;
while (l1!= null || l2!= null || sum!=0) {
if (l1!= null) {
sum += l1.val;
l1= l1.next;
}
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def resverse(self, head):
temp = None
cur = head
while cur:
nxt = cur.next
cur.next = temp
temp = cur
cur = nxt
return temp
def adding(self, headA, headB):
curA = headA
curB = headB
carry = 0
dummy = ListNode(1)
cur = dummy
while(curA and curB):
number = (curA.val + curB.val + carry) % 10
carry = (curA.val + curB.val + carry) // 10
cur.next = ListNode(number)
cur = cur.next
curA = curA.next
curB = curB.next
if curA: cur.next = curA
elif curB: cur.next = curB
反转+相加
先反转链表，相加得到结果后再反转
测试连接：445. 两数相加 II – 力扣（LeetCode）
时间复杂度：O(n+m)
空间复杂度：O(1)
思路：把两个链表转成数字 求和 然后把结果转成string以方便从开头开始取值 最后塞入新链表时把每一位转回int
比较python的做法 放别的语言可能要复杂点 包括考虑一百位的数字的数据类型等等
time O(n) space O(m+n)取决于结果数字的长度
思路：先翻转链表，逐位相加后，再把结果翻转。
class Node {
public:
int val;
Node* next;
};
class Solution{
public:
Node* f(Node* head){
if(head NULL) return head;
Node* pre = NULL;
Node* cur = head;
while(cur){
Node* temp = cur;
cur->next = pre;
pre = cur;
cur = temp->next;
}
return pre;
}
};
时间复杂度O(n+m)，空间复杂度O(1)。
先反转链表，从个位开始，再返回原状；
node* node_reserve(node* head){
node* pre=NULL;
node* cur=head;
while(cur){
node* next=cur->next;
cur->next=pre;
pre=cur;
cur=next; // Move to the next node
}
return pre; // Return the value of the new head
}
int doublelist_add(node *head1, node *head2)
{
node *reserve_head1 = node_reserve(head1);
node *reserve_head2 = node_reserve(head2);
node *cur1 = reserve_head1;
node *cur2 = reserve_head2;
int carry = 0;
int sum = 0;
int bit = 0;
int result = 0;
while (cur1 || cur2 || carry)
{
bit = bit? bit * 10:1;
int val1=cur1 ? cur1->val : 0;
int val2=cur2 ? cur2->val : 0; // Get the value of the current node or 0 if at the end of the list
sum = val1 + val2 + carry; // Calculate the sum of the current digits and the carry
carry = sum / 10;
sum %= 10;
result += bit * sum; // Add the current digit to the result
cout<<result<<endl; // Print the current result
cur1 = cur1 ? cur1->next : nullptr;
cur2 = cur2 ? cur2->next : nullptr; // Move to the next node in both lists or nullptr if at the end
}
}
int main(){
node* head=new node(1);
head->next=new node(2);
head->next->next=new node(3);
head->next->next->next=new node(4);
doublelist_add(head,head2);
// Clean up memory
node* temp;
while(head){
temp=head;
head=head->next;
delete temp;
}
while(head2){
temp=head2;
head2=head2->next;
delete temp;
}
return 0;
}
先反转,再相加,再反转
时间复杂度O(m+n)
空间复杂度O(m+n)
递归反转+递归相加
思路：先反转链表，再按位相加，这个过程中注意进位。最后再反转输出链表。
时间复杂度：o(n) 空间复杂度 0(n)
思路：反转两条链表，相加，同时记录进位
时间o(n+m)
空间o(1)
思路： 首先 将两个链表逆转，然后依次同时遍历两个链表，并计算当前位结果。 需要设置carry表示当前位进位情况，用于后续操作。计算得到的结果通过头插法 构成 ans 结果列表。 需要关注最后一位计算完成后，是否需要进位，若需要进位，需额外添加一个Node。
测试： 力扣 LCR 025. 两数相加 II LCR 025. 两数相加 II
思路：链表的节点是从高位到低位存储的，而两个数的加法则是从低位到高位进行运算的，因此需要先将两个链表反转；再对反转后的链表节点一一求和，并组成新链表；将构建的新链表再次反转，确保链表的顺序就是所求的解。
时间复杂度：O(n + m)，最大的时间复杂度则是在反转了两个链表。
空间复杂度：O(max(m, n))，两个链表求和后的链表的长度是两个链表的最大值（最多还要加 1）。