【链表专题】字节真题：单链表相加
本问题对应课程链接：剑指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 个回答
打卡成功
时间复杂度为O(m+n),空间复杂度为O(m+n)
//两数相加 先将数据链表反转再进行计算 两个链表中的对应位置中存在值则相加 得出的值得10位加1 得个位为当前值 在每次计算后计算下一位
public ListNode reverseList(LIstNode node)
{
ListNode pre=NULL;
ListNode q= NULL;
while(node!= NULL)
{
q= node.next;
node.next = pre;
pre= node;
node = q;
}
public ListNode addTwoNumbers(LIstNode l1,ListNode l2)
{
ListNode listnode = new ListNode(0);
ListNode p = listnode;
int sum=0;
while(l1!= NULL||l2!= NULL||sum0)
{
if(l1 != NULL)
{
sum += l1->val;
l1= l1->val;
}
if(l2!=NULL)
{
sum +=l2->val;
l2= l2->next;
}
p->next = new ListNode(sum%10);
sum =sum/10;
p= p->next;
}
return ListNode->next;
}
}
struct node *addTwoNumber(struct node * lane1,struct node * lane2)
{
struct node * dummy = (struct node *)malloc(sizeof(struct node));//创建dummy节点，最终结果的头节点
struct node * curr = dummy;
int carry = 0 ;
while(lane1 != NULL || lane2 != NULL)//遍历l1 l2，直到为空
{
int sum = carry;
if(lane1 != NULL)
{
sum += lane1->val;
lane1=lane1->next;
}
if(lane2 != NULL)
{
sum += lane2->val;
lane2=lane2->next;
}
curr->next = (struct node *)malloc(sizeof(struct node *));
curr = curr->next;//节点往下走，相加
curr->val = sum%10;//判断进位
carry = sum/10;
}
if(carry > 0)
{
curr->next = (struct node *)malloc(sizeof(struct node *));
curr = curr->next;
curr->val = carry;//如果遍历完，仍存在进位，则需要进行进位的值
}
curr->next = NULL;
struct node * due = dummy->next;
free(dummy);
return due;
}//时间复杂度为O(n)，空间复杂度为O(1)
leetcode445：先反转链表，再相加，再反转链表
时间复杂度：o(n)
空间复杂度：o(n)
#python题解：
#特殊场景：9->9 + 1->1->9
class Solution(object):
def addTwoNumbers(self, l1, l2):
“””
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
“””
head = ListNode(0)
cur = head
remaining = 0
while l1 or l2:
if l1 None:
cur.next = l2
#此处是为了将剩下的l2.val + 进位 + 0，使得加的l1不空，得到的remaining用作下一个节点的val和进位
l1 = ListNode(0)
if l2 None:
cur.next = l1
l2 = ListNode(0)
参考的力扣445. 两数相加 II
先将两个链表反转，然后进行列表相加，最后再反转一下。
时间复杂度为O(n)，空间复杂度为O(1)
思路：先将列表反转，相加后再次反转
//首先将俩链表进行反转；
//其次将反转链表的每个值相加，Count做为进位值。
//时间复杂度为o(n)
//空间复杂度为o(1)
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
};
思路：先反转两个链表，然后遍历两个链表，每次得到进位和一个当前位的值，使用当前位的值构造一个新节点并插入到插入到链表的头节点处，直到两个链表都遍历完并且进位为0
时间复杂度：O(N)，空间复杂度：O(N)
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverse(l1);
l2 = reverse(l2);
int sum = 0;
int flag = 0;
ListNode cur = null;
while(l1 != null || l2 != null || flag != 0) {
sum = sum + (l1 != null ? l1.val : 0);
sum = sum + (l2 != null ? l2.val : 0);
sum += flag;
flag = sum / 10;
sum %= 10;
ListNode temp = new ListNode(sum);
temp.next = cur;
cur = temp;
}
return cur;
}
//头插法反转链表
public ListNode reverseList(ListNode head) {
if(headnull)
return null;
ListNode temp = new ListNode(0);
ListNode pre = head;
时间复杂度
/**
* struct ListNode {
* int val;
* struct ListNode next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
ListNode ReverseList(ListNode *head) {
if (head nullptr) return nullptr;
ListNode *cur = head;
ListNode *pre = nullptr;
while (cur) {
// 断开链表,需要记录后续第一个节点位置
ListNode *next = cur->next;
// 将当前节点的next指向先前节点
cur->next = pre;
// 将先前节点更新为当前节点
pre = cur;
// 将当前节点更新为原链表中的下一个节点
cur = next;
}
return pre;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode reverseList(ListNode* head) {
if(headNULL||head->nextNULL){
return head;
}
ListNode pre=NULL,cur=head;
while(cur!=NULL){
ListNode t=cur->next;
cur->next=pre;
pre=cur;
cur=t;
}
return pre;
}
ListNode addList(ListNode* l1, ListNode* l2) {
nt jinwei=0;
ListNode* result=new ListNode(0);
ListNode* t=result;
while(l1!=NULL||l2!=NULL){
int n1 = l1 ? l1->val: 0;
int n2 = l2 ? l2->val: 0;
int sum=n1+n2+jinwei;
jinwei=sum/10;
if(l1!=NULL)
l1=l1->next;
if(l2!=NULL)
l2=l2->next;
t->next=new ListNode(sum%10);
t=t->next;
}
if (jinwei > 0) {
t->next = new ListNode(jinwei);
}
return result->next;
}
};
时间复杂度：O(n+m)
空间复杂度：O(1)
时间复杂度O(n)空间复杂度O(n)
反转链表的函数是用的前一天的代码
”’java
public ListNode addListNode(ListNode headA, ListNode headB)
{
if(headA null) return headB;
if(headB null) return headA;
ListNode* addList(ListNode* headA, ListNode* headB) {
if (!headA) return headB;
if (!headB) return headA;
}
時間複雜度: O(M+N), O(1)
核心: 維護一個sum 跟 carry 分別代表每次兩數相加的和跟要進位的數, 按照正常數學算法的邏輯去寫, 就挺容易, 最後答案要反轉才會是正確的
时间复杂度：O(n+m)，空间复杂度：O(1)
一开始想学之前的方法对t1和t2进行初始赋值，如：
但是这样赋值会导致t1原本就存在节点值为0，在后续相加时result会在开头多出值为0的结果，需要再去手动删去，不知道有没有更好的解决办法。
1.For this question, becasue we need add from the last,and we don’t have two direction linked list,
so we need parse this question in two problem (1)reserve linked list (2)add linked list
(1)
reserve need to consider prev and cur point
(2)
add need to consider capital and sum, how to handle Longer list and the last capital 差不多就是这样
没想到。先反转链表，再逐个相加
“`python
自己写是把求和和生成新节点联系在一起，对比参考代码之后发现我的做法很直白，对两个链表对应位置的节点相加，然后有进位就想对应的方法解决进位。参考代码的思想，主要需要解决的问题是动态的相加，相加的两个整数被存放在两个链表里，结果也要求被放在链表里，那么动态相加参照这样的结构：这是一个求和的过程，链表存储则按位相加，每一个位相加时，用一个sum变量存储位相加的值，值为sum%10（一个位只能存储<10的），然后生成新节点把结果存储下来。如果sum值大于等于10，则通过sum/10计算进位，进位是要与下一位计算相加的，所以下一位相加前用sum先把进位的1记录下来，然后循环前面操作。
class SolutionAdd {
// 反转链表
public ListNode reverseList(ListNode node){
pre = None
tmp = None
while tmp:
tmp = node.next
node.next = pre
pre =node
node = tmp
}
public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
if head1 None: return head2
if head2 None: return head1
head1 = reverseList(head1)
head2 = reverseList(head2)
head = ListNode(-1)
cur = ListNode(0)
cur = head.next
while head1 and head2:
if head1.val+head2.val >=10:
newnode = ListNode(1)
cur.val = cur.val+head1.val+head2.val -10
else:
cur.val = head1.val + head2.val
newnode = ListNode(0)
}
cur.next = newnode
cur = cur.next
head1 = head1.next
head2 = head2.next
if head1:cur.next = head2
if head2:cur.next = head1
}
return reverseList(head.next)
}
先反转两个列表，然后逐个相加；
时间复杂度O(n+m); 空间复杂度O(1)
class Solution(){
先反转再相加
main(){
reverseList(l1);
reverseList(l2);
ListNode dummy = new ListNode();
ListNode cur = dummy;
boolean addOne = false;
while(l1 != null && l2 != null){
Node node = new ListNode();
int sum = l1.val + l2.val;
if(addOne) sum++;
if(sum >= 10){
node.val = sum – 10;
addOne = true;
}else{
node.val = sum;
addOne = false;
}
cur.next = node;
cur = cur.next;
l1 = l1.next;
l2 = l2.next;
}
if(l1 != null){
cur.next = l1;
}else if(l2 != null){
cur.next = l2;
}
if(cur.next){
if(addOne){
cur.next.val++;
}
}
}
//fanzhuanhanshu1反转函数
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *p1=head;
struct ListNode *p2=NULL;
while(p1){
struct ListNode *pnext=p1->next;
p1->next=p2;
p2=p1;
p1=pnext;
//free(pnext);
}
return p2;
}
struct ListNode getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *pA=headA;
struct ListNode *pB=headB;
struct ListNode *newA=NULL;
struct ListNode *newB=NULL;
struct ListNode *newSum=NULL;
struct ListNode *Sum=NULL;
int temp=0;
/
if(!pA){
return pB;
} else if(!pB){
return pA;
}
else{//先反转；//pa= a b c d
}
时间复杂度：O(n+m),空间复杂度：O(n)
时间复杂度O(n)，空间复杂度O(n)