【链表专题】字节真题：单链表相加
本问题对应课程链接：剑指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
共以下 43 个回答
“ java
//简单粗暴的方法
public class Solution {
public ListNode addList(ListNode head1, ListNode head2){
if (head1null && head2null) return null;
else if(head1 null) return head2;
else if(head2 null) return head1;
ListNode rever1 = reverseList(head1);
ListNode rever2 = reverseList(head2);
return reverseList(addReverseList(rever1, rever2));
}
}
//反转链表
func resver(head *ListNode) *ListNode {
if head.Next nil || head nil {
return head
}
//逆置后的头节点
node := resver(head.Next)
head.Next.Next = head
head.Next = nil
return node
}
func twoSum(head1 *ListNode, head2 *ListNode) *ListNode {
l1 := resver(head1)
l2 := resver(head2)
l3 := &ListNode{}
ptr := l3
sum := 0
for l1 != nil || l2 != nil || sum != 0 {
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
ptr.Next = &ListNode{Val: sum % 10}
sum = sum / 10
ptr = ptr.Next
}
}
反转链表，相加后如果需要进位将下两个相加的节点中的一个val+1，如果下一个节点是null，再添加一个节点node.val=1
时间复杂度O(max(m, n))空间复杂度O(1)public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
//先翻转链表 从个位数相加
if(head1null)
{
return head2;
}
if(head2null)
{
return head1;
}
ListNode pre1=new ListNode(0);
ListNode pre2=new ListNode(0);
pre1.next=null;
pre2.next=null;
ListNode temp;
while(head1!=null)
{
temp=head1;
head1=head1.next;
temp.next=pre1.next;
pre1.next=temp;
}
while(head2!=null)
{
temp=head2;
head2=head2.next;
temp.next=pre2.next;
pre2.next=temp;
}
head1=pre1.next;
head2=pre2.next;
ListNode result=new ListNode(0);
temp=result;
int sum=0;
while(head1!=null||head2!=null||sum!=0)
{
if(head1!=null)
{
sum=sum+head1.val;
head1=head1.next;
}
if(head2!=null)
{
sum=sum+head2.val;
head2=head2.next;
}
temp.next=new ListNode(sum%10);
temp=temp.next;
sum=sum/10;
}
temp=result.next;
ListNode head=temp;
result.next=null;
while(head!=null)
{
temp=head;
head=head.next;
temp.next=result.next;
result.next=temp;
}
return result.next;
}
}
先反转两个待合并链表，新建节点作为合并后的链表，相加完值之后再反转回来
LC 两数相加
链表逆序存储，所以直接按照顺序进行计算就好了，就是在相加过程中要注意进位的问题。
然后在head前面可以用一个虚拟头节点，这样可以避免一些边界问题。
LC445 两数相加2
这里的数字是顺序存储的，所以需要做一个逆序的过程。因为加法运算是从个位开始计算的，但是链表顺序存储的话在表头的部分是高位，如果从高位开始进行加法运算就会不好计算进位。
进行逆序计算有两种方法：
1. 链表反转
2. 通过stack等其他数据结构进行结果的存储，然后进行加法运算
这题和剑指 Offer II 025. 链表中的两数相加是相同的题目。
### 链表反转
这里就是单纯得先对链表进行反转，然后使用上面两数相加的方法。
“`cpp
class Solution {
public:
ListNode* reverse(ListNode* head){
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* temp;
while(cur){
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode* dummyHead = new ListNode();
ListNode* cur = dummyHead;
int carry = 0;
while(l1 || l2){
int val = carry;
if(l1){
val += l1->val;
l1 = l1->next;
}
if(l2){
val += l2->val;
l2 = l2->next;
}
carry = val/10;
val = val%10;
cur->next = new ListNode(val);
cur = cur->next;
}
if(carry>0){
cur->next = new ListNode(carry);
cur = cur->next;
}
dummyHead->next = reverse(dummyHead->next);
return dummyHead->next;
}
};
时间复杂度 O(m+n) 空间复杂度O(1)
/**
* 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 { s1, s2;
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack
//push elements in l1 l2 to s1 s2
while(l1){
s1.push(l1->val);
l1 = l1->next;
}
while(l2){
s2.push(l2->val);
l2 = l2->next;
}
int res= 0;
ListNode* ans = nullptr;
while(!s1.empty() or !s2.empty() or res != 0){
int a = s1.empty() ? 0 : s1.top();
int b = s2.empty() ? 0 : s2.top();
if(!s1.empty()) s1.pop();
if(!s2.empty()) s2.pop();
//judge if cur > 10
int cur = a + b + res;
res = cur/10;
cur %= 10;
//建立新节点，头插法建立答案链表
auto p = new ListNode(cur);
p -> next = ans;
ans = p;
}
return ans;
}
};
时间复杂度：O（m+n）
空间复杂度：O（1）
class Solution {
public:
//反转链表
ListNode* reverseList(ListNode* head) {
if(!head||!head->next)return head;
};
一
时间复杂度： O（m+n）
空间复杂度：O（m+n)
打卡
时间复杂度：O（n+m）
空间复杂度：O（1）
”’java
class Solution {
public ListNode addReTwoNumbers(ListNode l1, ListNode l2) {
//单链表相加
//先将链表进行反转，再链表相加，最后把结果反转
l1 = reverseNode(l1);
l2 = reverseNode(l2);
ListNode head = addTwoNumbers(l1,l2);
return reverseNode(head);
}
}
”’
时间复杂度O(m+n)
空间复杂度O(1)
Day4：下面是代码
反转链表
首先反转两个链表，然后两个链表按顺序相加，生成新的链接，处理进位，最后将生成的新的链表返转并返回。
两种方案：
1. 反转链表
方案二：使用栈
时间复杂度：O(n);
空间复杂度：O(n);
TS做法
“`c++
/**
* 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* res(ListNode* head) //反转链表
{
ListNode *pre=NULL,*next=NULL;
while(head)
{
next=head->next;
head->next=pre;
pre=head;
head=next;
}
return pre;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1=res(l1);
l2=res(l2);
int ca = 0, n1 = 0, n2 = 0, n = 0;
ListNode *c1 = l1;
ListNode *c2 = l2;
ListNode *node = NULL;
ListNode *pre = NULL;
while (c1 || c2) {
n1 = c1 != NULL ? c1->val : 0;
n2 = c2 != NULL ? c2->val : 0;
n = n1 + n2 + ca;
pre = node;
node = new ListNode(n % 10);
node->next = pre;
ca = n / 10;
c1 = c1 != NULL ? c1->next : NULL;
c2 = c2 != NULL ? c2->next : NULL;
}
if (ca == 1) {
pre = node;
node = new ListNode(1);
node->next = pre;
}
return node;
}
};
Java 单链表相加
纯模拟，反转两遍
c++ 代码链表模拟加法
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode* head=new ListNode(1);
ListNode* h=head;
int sum=0;
while(l1||l2)
{
if(l1)
{
sum+=l1->val;
l1=l1->next;
}
if(l2)
{
sum+=l2->val;
l2=l2->next;
}
ListNode* temp=new ListNode(sum%10);
sum/=10;
h->next=temp;
h=h->next;
}
if(sum>0)
h->next=new ListNode(1);
return head->next;
}
};