【链表专题】字节真题：单链表相加-跟着帅地玩副业，开拓第二曲线PlayOffer

盖瑞永久会员 2024年5月31日下午11:14

反转链表 + 字符串相加

        public ListNode plus(ListNode head1, ListNode head2) {
            if (head1 == null) return head2;
            if (head2 == null) return head1;
            ListNode num1 = reverse(head1);
            ListNode num2 = reverse(head2);
            boolean jinwei = false;
            ListNode pre = new ListNode(-1);
            ListNode ans = pre;
            while (num1 != null || num2 != null || jinwei) {
                int num = jinwei ? 1 : 0;
                if (num1 != null) num += num1.val;
                if (num2 != null) num += num2.val;
                if (num >= 10) jinwei = true;
                else jinwei = false;
                pre.next = new ListNode(num % 10);
                if (num1 != null) num1 = num1.next;
                if (num2 != null) num2 = num2.next;
                pre = pre.next;
            }
            return reverse(ans.next);
        }

0 赞同 0 条回复

Deckkker 普通 2024年3月31日下午4:10

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if not l1 and not l2:
            return None
        # 反转链表
        r1 = self.reverseList(l1)
        r2 = self.reverseList(l2)

        dummy = ListNode(-1)    # 创建一个虚拟头节点
        carry = 0       # 进位
        cur = dummy     # 当前节点指针

        # 逐位相加
        while r1 or r2 or carry:
            x = r1.val if r1 else 0
            y = r2.val if r2 else 0
            total = x + y + carry
            carry = total // 10
            digit = total % 10

            cur.next = ListNode(digit)
            cur = cur.next

            if r1:
                r1 = r1.next
            if r2:
                r2 = r2.next

        # 再次反转链表并返回
        return self.reverseList(dummy.next)

    def reverseList(self, head):
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

时间复杂度：O(max(m, n))，m和n分别是两个链表的长度。
空间复杂度：O(1)，需要创建一个新的链表来存储结果。在最坏情况下，当两个链表的长度相等且每一位都产生进位时，结果链表的长度将达到max(m, n)，算法本身的空间复杂度是O(1)。

0 赞同 0 条回复

YOLO 普通 2024年3月12日下午7:58

class Solution{
        public ListNode add(ListNode L1,ListNode L2){
            ListNode new1 = reverse(L1);
            ListNode new2 = reverse(L2);
            int sum = 0;
            ListNode new = new ListNode(0);//定义新节点
            ListNode q = new;
            while(L1 != null || L2 != null || sum != 0 ){
                if(L1 != null){
                    sum += L1.val;
                    L1 = L1.next;
                }
                if(L2 != null){
                    sum += L2.val;
                    L2 = L2.next;
                }
                q.next = new ListNode(sum % 10);
                sum = sum / 10;
                q = q.next;
            }
            //返回结果链表的反转
            return reverse (new.next);
        }    
        ListNode reverse(ListNode node){
            //原地反转
            ListNode p = null;
            ListNode pre = null;
            while(node != null){
                p = node.next;
                node.next = pre;
                pre = node;
                node = p;
            } 
            return pre;
        }
    }

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月12日下午6:23

我学习了思路，思路就是将两个链表都反转，然后再进行运算。代码没写

0 赞同 0 条回复

kfaebot 普通 2024年3月12日上午11:03

struct LinkNode{
    int val;
    LinkNode *next;
    LinkNode(): val(0), next(nullptr){}
    LinkNode(int x):val(x),next(nullptr){}
    LinkNode(int x, LinkNode* next): val(0),next(next){}
};

class solution{
    public:
        LinkNode* reverse_head(LinkNode* head){
            LinkNode* tmp=nullptr;
            LinkNode* slow=nullptr;
            LinkNode* fast=head;

            if(head==nullptr||head->next==nullptr){
                return head;
            }

            while(fast!=nullptr){
                tmp=fast->next;
                fast->next=slow;
                slow=fast;
                fast=tmp;
            }
            return slow;
        }

        LinkNode* listnode_add(ListNode* head1, ListNode* head2){
            ListNode* head_reverse1=reverse_head(head1);
            ListNode* head_reverse2=reverse_head(head2);

            //创建哨兵节点
            ListNode* dum=new ListNode();
            ListNode* tmp=dum;

            //创建指针
            ListNode* ptr1=head_reverse1;
            ListNode* ptr2=head_reverse2;

            //进位
            int bitt=0;

            while(ptr1!=nullptr||ptr2!=nullptr){
                int x=(ptr1!=nullptr?ptr1->val:0);
                int y=(ptr2!=nullptr?ptr2->val:0);
                int sum=x+y+bitt;

                tmp->next=new ListNode(sum%10);
                tmp=tmp->next;

                bitt=sum/10;

                if(ptr1!=nullptr){
                    ptr1=ptr1->next;
                }
                if(ptr2!=nullptr){
                    ptr2=ptr2->next;
                }
            }
            if(bitt==1){
                tmp->next=new ListNode(bitt);
            }
            ListNode* res=reverse_head(dum->next);
            return res;
        }
//先反转再计算再反转
};

0 赞同 0 条回复

莫～慢～待普通 2024年3月9日下午6:38

class Solution {
ListNode reverse(ListNode node)
{
ListNode pre=null;
while(node!=null)
{
ListNode temp=node.next;
node.next=pre;
pre=node;
node=temp;
}
return pre;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode new_l1=reverse(l1);
ListNode new_l2=reverse(l2);
int jinwei=0;
ListNode temp_l1=new_l1;
ListNode temp_l2=new_l2;
ListNode head=new ListNode(-1);
ListNode new_temp=head;
while((temp_l1!=null)&&(temp_l2!=null))
{
int val=(temp_l1.val+temp_l2.val+jinwei)%10;
jinwei=(temp_l1.val+temp_l2.val+jinwei)/10;
new_temp.next=new ListNode(val);
new_temp=new_temp.next;
temp_l1=temp_l1.next;
temp_l2=temp_l2.next;
}
while(temp_l1!=null)
{
int val=(temp_l1.val+jinwei)%10;
jinwei=(temp_l1.val+jinwei)/10;
new_temp.next=new ListNode(val);
new_temp=new_temp.next;
temp_l1=temp_l1.next;
}
while(temp_l2!=null)
{
int val=(temp_l2.val+jinwei)%10;
jinwei=(temp_l2.val+jinwei)/10;
new_temp.next=new ListNode(val);
new_temp=new_temp.next;
temp_l2=temp_l2.next;
}
if(jinwei!=0)
{
new_temp.next=new ListNode(jinwei);
new_temp=new_temp.next;
}
return reverse(head.next);
}
}
先反转链表，然后链表相加，再把新链表反转回来

0 赞同 0 条回复

mpweixin用户普通 2024年3月8日上午10:15

class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pslow = head;
ListNode* pfast = head;
ListNode* pfastn = head;
if (head NULL || head->next NULL) {
return head;
}
pfast = head->next;
pfastn = head->next->next;
while (pfast != NULL) {
if (pslow head) {
pslow->next = NULL;
}
pfast->next = pslow;
pslow = pfast;
pfast = pfastn;
if (pfast NULL) {
break;
}
pfastn = pfastn->next;
}
return pslow;
}
ListNode* listAddition(ListNode* headA, ListNode* headB) {
ListNode* Ar = reverseList(headA);
ListNode* Br = reverseList(headB);
ListNode* Arc = Ar; ListNode* Brc = Br;
ListNode* ll; ListNode* llc;
while (Arc != NULL && Brc != NULL) {
Arc = Arc->next;
Brc = Brc->next;
}
if (Arc != NULL) {
ll = Ar;
}
else if (Brc != NULL) {
ll = Br;
}
else if (Arc NULL && Brc NULL) {
ll = Ar;
}
llc = ll;
int bit = 0;//进位
Arc = Ar; Brc = Br;
while (Arc != NULL && Brc != NULL) {
if ((Arc->val + Brc->val+bit) >= 10) {
ll->val = (Arc->val + Brc->val) – 10+bit;
bit = 1;
}
else {
ll->val = (Arc->val + Brc->val)+bit;
bit = 0;
}
Arc = Arc->next; Brc = Brc->next;
ll = ll->next;
}
ll->val += bit;
return reverseList(llc);
}
};

0 赞同 0 条回复

Yeah~ 普通 2024年3月7日上午12:17

“`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* addTwoNumbers(ListNode* l1, ListNode* l2) {

    if(l1 == nullptr) return l2;
    if(l2 == nullptr) return l1;
    ListNode* h1 = reverseList(l1);
    ListNode* h2 = reverseList(l2);
    ListNode* cur=nullptr, * ret=nullptr;
    int carry = 0;
    for(int sum, val; h1 != nullptr || h2 != nullptr;
        h1=h1==nullptr?nullptr:h1->next,
        h2=h2==nullptr?nullptr:h2->next){

        sum = (h1==nullptr?0:h1->val)+(h2==nullptr?0:h2->val)+carry;
        val = sum%10;
        carry = sum/10;
        if(ret==nullptr){
            ret = new ListNode(val);
            cur = ret;
        }else{
            cur->next = new ListNode(val);
            cur = cur->next;
        }

    }
    if(carry==1){
        cur->next = new ListNode(1);
    }
    ListNode* ans = reverseList(ret);
    return ans;
}

ListNode* reverseList(ListNode* list){
    if(list == nullptr || list->next ==nullptr){
        return list;
    }
    ListNode* cur, * pre, * post;
    cur = post = list;
    pre = nullptr;
    while(post){
        post= post->next;
        cur->next = pre;
        pre = cur;
        cur = post;
    }
    return pre;
}

};

时间O(m+n)
空间O(1)

“`

0 赞同 0 条回复

e=mc² 普通 2024年3月6日下午11:12

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 原地反转
        ListNode curr = l1;
        ListNode pre = null;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        // 递归反转
        ListNode pre2 = reverse(l2);

        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        // 进位
        int carry = 0;
        // 同时满足三个条件
        while (pre != null || pre2 != null || carry != 0) {
            int sum = carry;
            if (pre != null) {
                sum += pre.val;
                pre = pre.next;
            }
            if (pre2 != null) {
                sum += pre2.val;
                pre2 = pre2.next;
            }
            carry = sum / 10;
            sum %= 10;
            current.next = new ListNode(sum);
            current = current.next;
        }

        // 返回结果链表的反转
        return reverse(dummy.next);

    }

    public ListNode reverse(ListNode l2) {
        if (l2 == null || l2.next == null) {
            return l2;
        }
        ListNode temp = reverse(l2.next);
        l2.next.next = l2;
        l2.next = null;
        return temp;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

1 赞同 0 条回复

30tcq 普通 2024年3月6日下午4:18

//单链表相加
//思路：先将两个链表反转，再相加，然后再反转
#include
using namespace std;
struct ListNode{
ListNode head;
int val;
ListNode(int val):val(val){}
};
class solution{
ListNode reverse(ListNode *l){
ListNode *pre, *cur;
pre = NULL, cur = l;
while(cur != NULL){
ListNode * next = cur->next;
cur->next = pre;
pre = cur;
cur = next;

    }
    return pre;
}
ListNode* addList(ListNode *l1, ListNode *l2){
    // 反转l1, l2
    ListNode *rl1, *rl2;
    rl1 = reverse(l1), rl2 = reverse(l2);

    // 链表相加
    ListNode *rrs;
    ListNode *cur1, *cur2, *cur;
    cur1 = rl1, cur2 = rl2, cur = rrs;
    int add = 0;
    while(cur1 || cur2){
        cur->val = (add + cur1 ? cur1->val : 0 + cur2 ? cur2->val : 0)%10;
        add = (cur1 ? cur1->val : 0 + cur2 ? cur2->val : 0) / 10;
        if(add || cur1->next || cur2->next){
            cur->next = new ListNode();
        }
        cur = cur->next;
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
     ListNode *rs = reverse(rrs);
     return rs;
}

}
int main(){

reutrn 0;

}
时间复杂度O(n）
空间复杂度O(n）

0 赞同 0 条回复

=.= 普通 2024年3月6日下午3:58

/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head1 = reverse(l1);
ListNode head2 = reverse(l2);
ListNode head = new ListNode(-1);

    ListNode p1 = head1;
    ListNode p2 = head2;
    ListNode p = head;

    int carry = 0;

    while(p1 != null && p2 != null){
        int temp = p1.val + p2.val + carry;
        if(temp >= 10){
            p.next = new ListNode(temp - 10);
            carry = 1;
        }
        else{
            p.next = new ListNode(temp);
            carry = 0;
        }
        p = p.next;
        p1 = p1.next;
        p2 = p2.next;
    }

    if(p1 != null){
        while(p1 != null){
            int temp = p1.val + carry;
            if(temp >= 10){
                p.next = new ListNode(temp - 10);
                carry = 1;
            }
            else{
                p.next = new ListNode(temp);
                carry = 0;
            }
            p = p.next;
            p1 = p1.next;
        }
    }

    if(p2 != null){
        while(p2 != null){
            int temp = p2.val + carry;
            if(temp >= 10){
                p.next = new ListNode(temp - 10);
                carry = 1;
            }
            else{
                p.next = new ListNode(temp);
                carry = 0;
            }
            p = p.next;
            p2 = p2.next;
        }
    }

    if(p1 == null && p2 == null && carry != 0){
        p.next = new ListNode(carry);
    } 

    return reverse(head.next);
}

public ListNode reverse(ListNode head){
    if(head == null) return head;

    ListNode pre = null;
    ListNode cur = head;

    while(cur != null){
        ListNode node = cur.next;
        cur.next = pre;
        pre = cur;
        cur = node;
    }

    return pre;
}

}

———————————分割线———————————————————

/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head1 = reverse(l1);
ListNode head2 = reverse(l2);
ListNode head = new ListNode(-1);

    ListNode p1 = head1;
    ListNode p2 = head2;
    ListNode p = head;

    int carry = 0;

    while(p1 != null || p2 != null || carry != 0){
        if(p1 != null){
            carry += p1.val;
            p1 = p1.next;
        }
        if(p2 != null){
            carry += p2.val;
            p2 = p2.next;
        }
        System.out.println(carry%10);
        p.next = new ListNode(carry%10);
        carry /= 10;
        p = p.next;
    }

    return reverse(head.next);
}

public ListNode reverse(ListNode head){
    if(head == null) return head;

    ListNode pre = null;
    ListNode cur = head;

    while(cur != null){
        ListNode node = cur.next;
        cur.next = pre;
        pre = cur;
        cur = node;
    }

    return pre;
}

}

时间复杂度：O(m+n)
空间复杂度：O(1)

0 赞同 0 条回复

一颗红豆普通 2024年3月5日下午2:10

完整的创建数据结构及实现反转链表与对应位相加的c++代码
#include
#include
using namespace std;
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){}
};
void tailinsert(ListNode *head,int n) //尾插法构建链表输入头节点及链表长度
{
if(headnullptr)
{
cout<<“head is null”<<endl;
return;
}
ListNode *p=head;
for(int i=0;i<n;i++)
{
ListNode *q=new ListNode;
q->val = i;
q->next=nullptr;
p->next=q;
p=q;
}

}
ListNode * headinsert(ListNode *head,int n) //头插法构建链表输入头节点及链表长度
{

for(int i=n;i>0;i--)
{
    ListNode *q=new ListNode;
    q->val = i;
    q->next = head;
    head = q;
}
return head;

}
void printlist(ListNode *head) //打印链表
{
int num = 0;
ListNode *p= head;
while(p!=nullptr)
{
p=p->next;
num++;
}
vector a(num);
p =head;
for(int i=0;i<num;i++)
{
a[i] = p->val;
p = p->next;
cout<<a[i]<<endl;
}

}
ListNode *reverseList(ListNode *head) //反转链表
{
if(headnullptr)
{
return head;
}
ListNode *cur=head;
ListNode *pre=nullptr;
ListNode *temp = head->next;
while(cur!=nullptr)
{
cur->next = pre;
pre = cur;
cur = temp;
temp = tempnullptr?nullptr:temp->next;
}
return pre;

}
int addlist(ListNode l1,ListNode *l2) //求链表之和
{
int sum = 0;
ListNode *temp1 = l1;
ListNode *temp2 = l2;
while(temp1!=nullptr&&temp2!=nullptr)
{
sum+=(temp1->val+temp2->val);
temp1 = temp1->next;
temp2 = temp2->next;
}
while(temp1!=nullptr)
{
sum+=temp1->val;
temp1 = temp1->next;
}
while(temp2!=nullptr)
{
sum+=temp2->val;
temp2 = temp2->next;
}
return sum;
}
ListNode *AddList(ListNodel1,ListNode*l2) //两链表合并后的链表
{
int sum =0;
ListNode * result =new ListNode(0);
ListNode *temp = result;
while(l1!=nullptr||l2!=nullptr||sum!=0)
{
if(l1!=nullptr)
{
sum+=l1->val;
l1 = l1->next;
}
if(l2!=nullptr)
{
sum+=l2->val;
l2 = l2->next;
}
ListNode *newnode = new ListNode(sum%10);
temp->next = newnode;
sum = sum/10;
temp = temp->next;
}
return result->next;

}
int main() {
ListNode *l = new ListNode(5);
ListNode *l1 = new ListNode(7);
tailinsert(l,3);
l1 = headinsert(l1,5);
printlist(l);
printlist(l1);
ListNode *reversel = reverseList(l);
ListNode *reversel1 = reverseList(l1);
cout<<“翻转后”<<endl;
printlist(reversel);
printlist(reversel1);
cout<<“链表相加”<<endl;
cout<<addlist(reversel,reversel1)<<endl;;
cout<<“相加后的链表”<<endl;
ListNode *newlist = AddList(reversel,reversel1);
printlist(newlist);
cout<<“最终反转”<<endl;
ListNode *l2 = reverseList(newlist);
printlist(l2);
return 0;
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月5日上午11:10

思路：
先反转两链表，然后构建一个虚拟节点保存进位，定义sum来存储相加的和模10来存储进位

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月5日上午10:18

时间：O(m+n)
空间：O(1)

class Solution {
public:
    // 翻转链表
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
    ListNode* addTwoNumbers(ListNode* head1, ListNode* head2) {
        head1 = reverseList(head1), head2 = reverseList(head2); // 翻转两个链表
        ListNode* dummyhead = new ListNode;
        ListNode* cur = dummyhead;
        int sum = 0, mov = 0; // 定义本位和 与 进位
        while(head1 || head2) {
            int n1 = head1 ? head1->val : 0;
            int n2 = head2 ? head2->val : 0;
            sum = n1 + n2 + mov; // 本位和：n1+n2+进位
            cur->next = new ListNode(sum % 10); // 构建新的和节点
            mov = sum / 10; // 计算进位

            cur = cur->next;
            if(head1) head1 = head1->next;
            if(head2) head2 = head2->next;
        }
        if(mov > 0) cur->next = new ListNode(mov); // 最后还有进位，单独构建一个点
        ListNode* newHead = reverseList(dummyhead->next);
        return newHead;
    }
};

0 赞同 0 条回复

晚风、普通 2024年3月5日上午12:32

class Node():
def init(self, val=0, next=None):
self.val = val
self.next = next
class Solution():
def reverse_list(self,head):
#双指针法
cur,pre = head,None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre

def add_two_nodelist(self,head1,head2):
    cur1 = head1
    cur2 = head2
    sumNode = headNode = Node(-1)
    jinwei = 0
    while cur1 and cur2:
        sum_value = cur1.val + cur2.val + jinwei
        if sum_value > 9:
            jinwei = 1
            sum_value %= 10
        else:
            jinwei = 0
        node_add = Node(sum_value)
        sumNode.next = node_add
        sumNode = sumNode.next
        cur1 = cur1.next
        cur2 = cur2.next
    shenyu = Node(-1)
    if cur1:
        shenyu = cur1
    elif cur2:
        shenyu = cur2
    sum_shenyu = sum_shenyu_real = Node(0)
    while shenyu:
        sum_1 = shenyu.val + jinwei
        #import pdb;pdb.set_trace()
        if sum_1 > 9:
            jinwei = 1
            sum_1 %= 10
        else:
            jinwei = 0
        add_node1 = Node(sum_1)
        sum_shenyu.next = add_node1
        sum_shenyu = sum_shenyu.next
        shenyu = shenyu.next
    if jinwei:
        add_node1 = Node(1)
        sum_shenyu.next = add_node1
    sumNode.next = sum_shenyu_real.next
    return headNode.next

def produce_nodelist(self,list1):
    head_using = head = Node(-1)
    for i in list1:
        node = Node(i)
        head.next = node
        head = head.next
    return head_using.next

def run(self):
    #生成链表
    list1 = [9,9]
    list2 = [9,9,9]
    listNode1 = self.produce_nodelist(list1)
    listNode2 = self.produce_nodelist(list2)
    # print("listNode1 is ")
    # while listNode1:
    #     print(listNode1.val)
    #     listNode1 = listNode1.next

    #反转链表
    listNode3 = self.reverse_list(listNode1)
    listNode4 = self.reverse_list(listNode2)

    #链表相加
    resNode = self.add_two_nodelist(listNode3,listNode4)
    resNode = self.reverse_list(resNode)
    print("resNode is ")
    while resNode:
        print(resNode.val)
        resNode = resNode.next

if name “main“:
perf = Solution()
perf.run()

思路：
1.使用双指针法，反转两个链表
2.两个链表相加：当两个链表指向都不为空时候，进行相加；将剩余没加的部分与进位相加得到剩余部分。

0 赞同 0 条回复

Jimmy 普通 2024年3月4日下午9:56

先对两个单链表进行反转，然后对反转后的两个链表相加，最后将相加后的结果链表再次反转。
时间复杂度：O(n+m)
空间复杂度：O(1)

#include <iostream>
#include <string>
#include <stdlib.h>
#include <vector>
using namespace std;


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* reverseList(ListNode *head){
        if(head == nullptr || head->next == nullptr);
        ListNode *cur = head,*pre = nullptr;
        while(cur != nullptr){
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    ListNode* addTwoNumbers(ListNode *head1,ListNode *head2){
        ListNode *dummyHead = new ListNode(0);
        ListNode *cur = dummyHead;

        int sum = 0;
        while(head1 != nullptr || head2 != nullptr || sum != 0){
            if(head1 != nullptr){
                sum += head1->val;
                head1 = head1->next;
            }
            if(head2 != nullptr){
                sum += head2->val;
                head2 = head2->next;
            }
            cur->next = new ListNode(sum%10);
            sum /= 10;
            cur = cur->next;
        }
        return dummyHead->next;
    }
};

ListNode* createList(vector<int> nums){
    ListNode *dummyHead = new ListNode(0);
    ListNode *cur = dummyHead;
    for(int i = 0; i < nums.size(); i++){
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return dummyHead->next;
}

void printList(ListNode *head){
    ListNode *cur = head;
    while(cur){
        cout<<cur->val<<" ";
        cur = cur->next;
    }
    cout<<endl;
}


int main()
{
    Solution solution;
    ListNode *head1 = createList(vector<int>{1,2,3,4});
    printList(head1);
    ListNode *head2 = createList(vector<int>{3,9});
    printList(head2);
    ListNode *reverseHead1 = solution.reverseList(head1);
    ListNode *reverseHead2 = solution.reverseList(head2);

    ListNode *reverseHead1_2 = solution.addTwoNumbers(reverseHead1,reverseHead2);
    ListNode *newHead = solution.reverseList(reverseHead1_2);

    ListNode *cur = newHead;
    printList(newHead);
    system("pause");
    return 0;
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月4日下午9:49

也可以用用ArrayDeque

0 赞同 0 条回复

神经蛙普通 2024年3月4日下午9:24

写下思路吧:
先把两个链表反转，从头到尾一次把两个链表节点的值相加，创建新节点，新节点的值为和对10取余，下一个节点的值需要加上前一个节点值对10取整，直到两个链表都为空

0 赞同 0 条回复

　南木普通 2024年3月4日下午8:44

思路：链表反转，然后从头到尾依次相加，出现大于10的取余并标记进位，循环到指向两个链表的指针都为空

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月4日下午8:14

class solution{
    public ListNode AddTwoLists(ListNode head1, ListNode head2 ){
        if(head1==null) return head2;
        if(head2==null) return head1;

        ListNode rhead1 = ReverseList(head1);
        ListNode rhead2 = ReverseList(head2);
        ListNode head3 = new ListNode(-1);
        ListNode newhead=head3;
        int newval=0;
        int res=0;

        while(rhead1!=null || rhead2!=null){

            newval=res;
            if(rhead1!=null){
                newval+=rhead1;
            }
            if(rhead2!=null){
                newval+=rhead2;
            }

            if(newval>=10){
                res=1;
            }else{
                res=0;
            }
            head3.next=new ListNode(newval);
            head3=head3.next;

            rhead1=rhead1.next==null ? null :rhead1.next;
            rhead2=rhead2.next==null ? null :rhead2.next;
        }

        return newhead;
    }

    public ListNode ReverseList(ListNode head){

        if(head==null || head.next==null ) return head;

        ListNode p=head;
        ListNode r=head.next;
        ListNode q;
        //链表倒转
        p.next=null;
        while(r!=null){
            q=r.next;
            r.next=p;
            p=r;
            r=q;
        }
        return p;
    }

}

时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

言之命至普通 2024年3月4日下午7:56

 public static ListNode removeNthFromEnd(ListNode l1, ListNode l2) {
        ListNode l11 = reverse(l1);
        ListNode l12 = reverse(l2);
        ListNode dummy = new ListNode(0); // 创建一个虚拟的头节点
        ListNode l13 = dummy; // l13 指向 dummy 节点

        int carry = 0; // 进位

        while (l11 != null || l12 != null || carry != 0) {
            int sum = (l11 != null ? l11.val : 0) + (l12 != null ? l12.val : 0) + carry;
            carry = sum / 10; // 计算进位
            l13.next = new ListNode(sum % 10); // 创建新节点存储当前位的值
            l13 = l13.next;

            if (l11 != null) {
                l11 = l11.next;
            }
            if (l12 != null) {
                l12 = l12.next;
            }
        }

        return reverse(dummy.next); // 返回翻转后的链表

    }

    public static ListNode reverse(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        // 反转子链表
        ListNode temp = reverse(head.next);
        head.next.next = head;
        head.next = null;

        return temp;
    }

时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

Jankin 普通 2024年3月4日下午6:28

留坑，后续再学。

0 赞同 0 条回复

普通 2024年3月4日下午5:35

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;
}

}
打卡

0 赞同 0 条回复

南梁陈庆之普通 2024年3月4日下午5:17

对两个链表进行反转，然后从头相加值，创建链表；遍历两个链表的时候，注意相加值大于10时取余，并相加进位值
时间复杂度O(N)
空间复杂度O(N)

class SolutionAdd {
    public ListNode  reverseList(ListNode node){
        ListNode cur = node, pre = null;
        while (cur != null) {
            ListNode tmp = cur.next,    
            cur.next = pre;
            pre = cur;
            cur = tmp
        }
        return pre;

    }

    public ListNode  addTwoNumbers(ListNode head1, ListNode head2) {
        ListNode rever1 = reverseList(head1);
        ListNode rever2 = reverseList(head2);

        ListNode addNode = new ListNode(0);
        ListNode cur = addNode;
        int sum = 0;
        while (rever1 != null || rever2 != null || sum != 0) {
            if (rever1 != null) {
                sum += rever1.val;
                rever1 = rever1.next;
            }
            if (rever2 != null) {
                sum += rever2.val;
                rever2 = rever2.next;
            }
            cur.next = new ListNode(sum % 10);
            sum = sum / 10;
            cur = cur.next;
        }
        return reverseList(addNode.next);      
    }
}

0 赞同 0 条回复

Fancy 普通 2024年3月4日下午5:01

#####第二版：提取公用方法
class Solution:
def reverseList(self, dummy):
head = dummy.next
cur = head; pre = dummy
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
head.next = None
return pre
def sumList(self, head1, head2):
dummy = ListNode(-1)
p = dummy
cur1 = head1; cur2 = head2
remainder = 0; summ = 0
while cur1 or cur2:
if cur1 and cur2:
summ = cur1.val + cur2.val + remainder
cur1 = cur1.next
cur2 = cur2.next
elif cur1:
summ = cur1.val + remainder
cur1 = cur1.next
elif cur2:
summ = cur2.val + remainder
cur2 = cur2.next
if summ < 10:
remainder = 0
p.next = ListNode(summ)
else:
remainder = 1
p.next = ListNode(summ-10)
p = p.next
if remainder 1:
p.next = ListNode(1)
return dummy.next
def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
# 先分别反转两个链表，然后对应相加，加完之后再反转回来得到新链表
# 翻转head1
dummy = ListNode(-1)
dummy.next = head1
newHead1 = self.reverseList(dummy)
# 翻转head2
dummy.next = head2
newHead2 = self.reverseList(dummy)
# 求和
newList = self.sumList(newHead1, newHead2)
# 再取反
dummy.next = newList
return self.reverseList(dummy)

第一版：杂乱

class Solution:
def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
# 先分别反转两个链表，然后对应相加，加完之后再反转回来得到新链表
dummy = ListNode(-1)
dummy.next = head1
cur = head1; pre = dummy
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
newHead1 = pre
head1.next = None

    # 翻转head2
    dummy.next = head2
    cur = head2; pre = dummy
    while cur:
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    newHead2 = pre; head2.next = None
    # 求和
    cur1 = newHead1; cur2 = newHead2
    dummy.next = cur1; pre =dummy
    remainder = 0
    while cur1 and cur2:
        summ = cur1.val + cur2.val + remainder
        if summ < 10:
            remainder = 0
            cur1.val = summ
        else:
            remainder = 1
            cur1.val = summ - 10
        cur1 = cur1.next
        cur2 = cur2.next
        pre = pre.next
    while cur1:
        summ = cur1.val + remainder
        if summ >= 10:
            remainder = 1
            cur1.val = summ - 10
            if not cur1.next:
                cur1.next = ListNode(1)
                break
            cur1 = cur1.next
        else:
            cur1.val = summ
            break
    if cur2:
        pre.next = cur2
        while cur2:
            summ = cur2.val + remainder
            if summ >= 10:
                remainder = 1
                cur2.val = summ - 10
                if not cur2.next:
                    cur2.next = ListNode(1)
                    break
                cur2 = cur2.next
            else:
                cur2.val = summ
                break
    # 再取反
    dummy.next = newHead1
    cur = newHead1; pre = dummy
    while cur:
        temp = cur.next
        cur.next = pre
        pre = cur
        cur = temp
    newHead1.next = None
    return pre

0 赞同 0 条回复

方铎码农普通 2024年3月4日下午3:34

import java.util.ArrayList;

public class SingleLinkedListAdd {

    public static class ListNode{
        int val;
        ListNode next;

        public ListNode(){}
        public ListNode(int x){
            this.val = x;
        }
        public ListNode(int val, ListNode next) {
            this.val = val; this.next = next;
        }
    }

    public static ListNode createList(int[] nums){
        ListNode res = new ListNode(0);
        ListNode pre = res;
        for(int i = 0; i < nums.length; i++){
            pre.val = nums[i];
            pre.next = new ListNode(0);
            pre = pre.next;
        }
        return res;
    }

    public static 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 static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int sum = 0;  //进位符号
        //数字是逆序方式存储的

        while(l1 != null || l2 != null || sum != 0){
            if(l1 != null){
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null){
                sum += l2.val;
                l2 = l2.next;
            }

            cursor.next = new ListNode(sum % 10);
            sum /= 10;
            cursor = cursor.next;
        }
        return root.next;
    }
    public static void main(String[] args) {
        int[] nums1 = {1,2,3,4};
        int[] nums2 = {3,4,5};
        ListNode l1 = createList(nums1);
        ListNode l2 = createList(nums2);
        ListNode sum = reverseList(addTwoNumbers(l1,l2));
        ArrayList<Integer> out = new ArrayList<>();
        for(ListNode head = sum; head.next != null; head = head.next){
            out.add(head.val);
        }System.out.println(out);
    }
}

0 赞同 1 条回复

方铎码农普通 @ 方铎码农 2024年3月4日下午3:36

时间复杂度$O(n)$，空间复杂度$O(n)$

登录以回复

lucky耶耶耶*👻*～普通 2024年3月4日下午2:26

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;
    }
}

0 赞同 0 条回复

Raphtalia. 普通 2024年3月4日下午2:01

class Solution {
public:
Node* copyRandomList(Node* heada, Node* headb) {
if(!heada) return headb;
if(!headb) return heada;
reverse(heada);
reverse(headb);
Node* head = new Node(0);
Node* tmp = head;
while(!heada && !headb){
tmp->val = heada->val + headb->val;
Node* tmp2 = new Node();
tmp->next = tmp2;
tmp = tmp2;
}
if(heada) tmp->next = head;
if(headb) tmp->next = head;
reverse(head);
return head;
}
Node* reverse(Node* head) {
Node* pre = nullptr;
Node* cur = head;
while(cur){
Node* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
时间复杂度O(N+M),空间复杂度O（1）

0 赞同 0 条回复

Yuki 永久会员 2024年3月4日下午12:20

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
/
ListNodereverseList(ListNodehead){
if(headnullptr)return nullptr;
ListNodepre=nullptr;
ListNode*cur=head;

    while(cur!=nullptr){
        ListNode*tmp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=tmp;
    }
    return pre;
}
ListNode* addInList(ListNode* head1, ListNode* head2) {
    // write code here
    //其中一条为空，直接返回
    if(head1==nullptr)return head1;
    if(head2==nullptr)return head2;
    //翻转链表
    head1=reverseList(head1);
    head2=reverseList(head2);

    int carry=0;//记录进位
    ListNode* dummyhead=new ListNode(0);//新链表虚拟头节点
    ListNode*cur=dummyhead;//遍历指针


    //只要有一条链表还不为空，或者还存在进位
    //一条链表先空，对应位置相当于0
    while(head1!=nullptr||head2!=nullptr||carry!=0){
        int val1=(head1==nullptr)?0:head1->val;
        int val2=(head2==nullptr)?0:head2->val;
        int res=val1+val2+carry;

        res%=10;//该位置的值
        carry=res/10;//进位

        cur->next=new ListNode(res);//尾插建表
        cur=cur->next;

        //向下移动一位
        if(head1!=nullptr)head1=head1->next;
        if(head2!=nullptr)head2=head2->next;
    }
    return reverseList(dummyhead->next);

}

};
时间复杂度：O(n+m)
空间复杂度：O(n)

0 赞同 0 条回复

紫芝普通 2024年3月4日上午9:21

时间复杂度：O(n+m)
空间复杂度：O(n+m)

“`c++
#include

using namespace std;

struct Node {
int val;
Node *next;
Node(int val): val(val), next(nullptr) {}
Node(): val(0), next(nullptr) {}
};

Node* reverse(Node* head, int &len) {
len = 0;
if (!head || !head->next) return head;
Node prehead = nullptr;
while (head) {
// cout << head->val << ” “;
len++;
Node tmp = head->next;
head->next = prehead;
prehead = head;
head = tmp;
}
// cout << endl;
return prehead;
}

int add(Node* head1, Node* head2) {
int len1 = 0;
head1 = reverse(head1, len1);
// cout << “len1: ” << len1 << endl;
int len2 = 0;
head2 = reverse(head2, len2);
int maxlen = max(len1, len2);
int sum[maxlen] = {0};
int idx = maxlen – 1;
int c = 0;
while (head1 || head2) {
if (head1) {
c += head1->val;
head1 = head1->next;
}
if (head2) {
c += head2->val;
head2 = head2->next;
}
sum[idx] = c % 10;
idx–;
c /= 10;
}
int res = 0;
for (int i=0; i<maxlen; ++i) {
res = res * 10 + sum[i];
}
return res;
}

int main() {
Node *head = new Node(1);
Node *cur = head;
for (int i=0; i<4; ++i) {
cur->next = new Node(i);
cur = cur->next;
}
Node *head2 = new Node(2);
cur = head2;
for (int i=4; i<9; ++i) {
cur->next = new Node(i);
cur = cur->next;
}
int res = add(head, head2);
cout << “res: ” << res << endl;
res = add(head, nullptr);
cout << “res: ” << res << endl;
return 0;
}

“`

0 赞同 0 条回复

😴 普通 2024年3月4日上午9:17

class SolutionAdd {
// 反转链表
public static ListNode reverse(ListNode a) {
ListNode slow = a;
ListNode pre = null;
if(a null) return a;
while (slow != null){
ListNode temp = slow.next;
slow.next = pre;
pre = slow;
slow = temp;

    }
    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;
        }

//注意是逆序相加因此于数给sum，进位给下一位
p.next = new ListNode(sum % 10);
sum = sum / 10;
p = p.next;
}
return listNode.next;
}
}
时间复杂度O(n+m)
空间复杂度 O(1)

0 赞同 0 条回复

Yox 普通 2024年3月4日上午12:15

// 注意，关于链表节点的定义（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)

0 赞同 0 条回复

Let it be 永久会员 2024年3月3日下午11:16

public void reverse(ListNode cur, ListNode pre){
if(cur null)return pre;
ListNode res = reverse(cur.next, cur);
cur.next = pre;
return res;
}

    public ListNode addTwoNumbers(ListNode head1, ListNode head2){
        ListNode head1 = reverse(head1, null);
        ListNode head2 = reverse(head2, null);
        int plus = 0;
        ListNode head = new ListNode(0);
        ListNode cur = head;
        while(head1 != null || head2 != null ){
            int opt1 = head1 != null ? head1.val : 0;
            int opt2 = head2 != null ? head2.val : 0;
            cur.next = new ListNode((opt1 + opt2 + plus)%10);
            plus = (opt1 + opt2 + plus)/10;
            head1 = head1 != null ? head1.next :null;
            head2 = head2 != null ? head2.next :null;
            cur = cur.next;
        }
        cur.next = plus != 0 ? new ListNode(1) :null;
        return reverse(head.next, null)
    }

时间复杂度O（N）空间复杂度O（1）

0 赞同 0 条回复

云无深雁影普通 2024年3月3日下午11:15

class Solution {
private ListNode rev(ListNode head){
if(head null)
return null;
ListNode pre = head;
ListNode cur = head.next;
ListNode temp = cur;
pre.next = null;
while(cur != null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode l1Rev = rev(l1);
    ListNode l2Rev = rev(l2);
    ListNode ans = new ListNode();
    ListNode ansPtr = ans;
    int carry = 0;
    while(l1Rev != null || l2Rev != null || carry != 0){
        int x = (l1Rev!=null ? l1Rev.val : 0) + (l2Rev!=null ? l2Rev.val : 0) + carry;
        carry = x>=10 ? 1 : 0;
        x = x % 10; 
        ansPtr.next = new ListNode(x);
        l1Rev = l1Rev!=null ? l1Rev.next : l1Rev;
        l2Rev = l2Rev!=null ? l2Rev.next : l2Rev;
        ansPtr = ansPtr.next;          
    }
    return rev(ans.next);
}

}
时间复杂度：O(n+m)
空间复杂度：O(n+m)

0 赞同 0 条回复

机电皮怪永久会员 2024年3月3日下午11:09


##CPP
时间复杂度o（3n）
空间复杂度o（n）
看了其他人的答案才想出来，感觉自己还是不熟练

class SolutionAdd{
public:
ListNode* reverse(ListNode* head) //反转链表
{
if(headnullptr || head->nextnullptr)
{
return head;
}
ListNode* newhead=reverse(head->next);
head->next->next=head;
head->next=nullptr;
return newhead;
}

ListNode* addTwoNumbers(ListNode* head1, ListNode* head2)
{
ListNode* tmphead1=reverse(head1);
ListNode* tmphead2=reverse(head2);
ListNode* dummyhead=new ListNode(0);
ListNode* cur=dummyhead;
int plus=0,sum=0;
while(tmphead1||tmphead2)
{
int num1=tmphead1nullptr?0:tmphead1->val;
int num2=tmphead2nullptr?0:tmphead2->val;
sum=num1+num2+plus;
if(sum>=10)
{
plus=sum/10;
sum=sum%10;
}
cur->next=new ListNode(sum,nullptr);
cur=cur->next;
tmphead1=tmphead1->next;
tmphead2=tmphead2->next;
}
if(plus>0)
{
cur->next=new ListNode(plus);
}
return reverse(dummyhead->next);
}
}

“`

0 赞同 0 条回复

东普通 2024年3月3日下午10:23

/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
// 反转链表
public ListNode reverseList(ListNode head){
ListNode pre = null;
ListNode cur= head;
while (cur != null) {
ne= node.next;
cur.next = pre;
pre = cur;
cur = ne;
}
return pre;
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode pre = new ListNode(0);
    int shi = 0;
    ListNode l1 = reverseList(l1);
    ListNode l2 = reverseList(l2);
    ListNode cur = pre;

    while(l1 != null || l2 != null){
        int x = l1 != null ? l1.val : 0;
        int y = l2 != null ? l2.val : 0;
        int sum = x + y + shi;
        shi = sum / 10;
        sum = sum % 10;
        cur.next = new ListNode(sum);
        cur = cur.next;
        if(l1 != null){
            l1 = l1.next;
        }
        if(l2 != null){
            l2 = l2.next;
        }
    }
    if(shi == 1){
        cur.next = new ListNode(1);
    }
    return pre.next;
}

}
跟leetcode2类似吧就是要先反转

0 赞同 0 条回复

MARS 普通 2024年3月3日下午10:23

day3第一题

class Node {
  constructor(val, node) {
    this.val = val === undefined ? 0 : val;
    this.next = node === undefined ? null : node;
  }
}
function reverse(prev, head) {  //翻转链表 prev head
  if (head === null) {
    return prev
  }
  let next = head.next
  head.next = prev
  prev = head
  return reverse(prev, next)  //一定记得return
}
function computedNodeVal(node1, node2) {
  let cur1 = reverse(null, node1)
  let cur2 = reverse(null, node2)
  let sum = 0   //记载两个节点相加的值，如果超过了10，可以继承给下一个节点
  let ans = new Node(0, null)  //虚拟节点
  let newHead = ans  
  while (cur1 !== null || cur2 !== null || sum != 0) { //一个不为空就继续运算
    if (cur1 !== null) {  //将val加到sum上
      sum += cur1.val
      cur1 = cur1.next
    }
    if (cur2 !== null) {
      sum += cur2.val
      cur2 = cur2.next
    }
    newHead.next = new Node(sum % 10, null)  //将sum取余
    sum = Math.floor(sum / 10)  
    newHead = newHead.next
  }
  return reverse(null,ans.next)
}
let node1 = new Node(1, new Node(2, new Node(3, new Node(4, undefined))))
let node2 = new Node(1, new Node(2, null))
console.log(computedNodeVal(node1, node2));

0 赞同 0 条回复

王位詮釋普通 2024年3月3日下午9:25

“`java
public class Solution {

public ListNode addTwoNumbers(ListNode head1,ListNode head2){
    head1 = reverse(head1);
    head2 = reverse(head2);
    int plus = 0;
    ListNode head = new ListNode();
    ListNode cur  = head;
    while(head1!=null||head2!=null){
        int operator1 = head1!=null?head1.val:0;
        int operator2 = head2!=null?head2.val:0;
        cur.next = new ListNode((operator1+operator2+plus)%10);
        plus = (operator1+operator2+plus)/10;
        head1 = head1!=null?head1.next:null;
        head2 = head2!=null?head2.next:null;
        cur = cur.next;
    }
    cur.next = plus!=0?new ListNode(1):null;
    return reverse(head.next);
}

public ListNode reverse(ListNode head){//反转链表
    if (head==null||head.next==null){
        return head;
    }
    ListNode newHead = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

}
思路：
错误：刚开始以为可以直接解决，然后想的是能不能递归，递归最深时候就是最后一个节点，刚好从最后一个节点开始相加，但是两个链表长度可能不一样，不可能让两个链表递归的同时找到对应的相加节点；
正确：先将两个链表进行反转，反转之后，头节点那里就直接是开始相加的位数，然后直接可以将两条链表视为一样长，如果是null的话直接让对应操作数为0，然后相加获得对应位数的值以及进位，进位参与下一个节点的加法中。
最后获得的链表反转之后返回就是结果

0 赞同 0 条回复

进取普通 2024年3月3日下午9:05

思路：1 写一个翻转链表的函数(双指针写的)
2 传入两个头指针，翻转
3 while循环两个链表相加循环判断条件 h1 || h2 有一个不为空都可进行
4 内部判断 h1指向空新链表指下一个结点指向l2 h1指向空反之
5 新链表判断结点/10 后一个结点的值加前结点/10
6 翻转新链表

0 赞同 0 条回复

heathhou 普通 2024年3月3日下午9:04

class Solution {
public:
    // 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode * cur = head;
        ListNode * pre = nullptr;

        while(cur != nullptr){
            ListNode * temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    // 单链表相加
    ListNode* addTwoNumbers(ListNode* head1, ListNode* head2){
        ListNode* head = new ListNode(0);
        ListNode* p = head;

        int sum = 0;
        while(head1 || head2 || sum != 0){
            if(head1){
                sum += head1->val;
                head1 = head1->next;
            }
            if(head2){
                sum += head2->val;
                head2 = head2->next;
            }

            p->next = new ListNode(sum % 10);
            sum = sum / 10;

            p = p->next;

        }

        return head->next;

    }

    ListNode* main(ListNode* head1, ListNode* head2){
        ListNode* head1 = reverseList(head1);
        ListNode* head2 = reverseList(head2);

        ListNode* head = addTwoNumbers(head1, head2);
        return reverseList(head);
    }
};

时间复杂度：O(n + m)
空间复杂度：O(n)

0 赞同 0 条回复

Free 普通 2024年3月3日下午8:49

ListNode* reverse(ListNode* list)
{
    if (list == nullptr || list->next == nullptr)
        return list;
    ListNode* newhead = reverse(list->next);
    list->next->next = list;
    list->next = nullptr;
    return newhead;
}

ListNode* Add(ListNode* list1, ListNode* list2)
{
    ListNode* reverselist1 = reverse(list1);
    ListNode* reverselist2 = reverse(list2);
    ListNode* newhead = new ListNode();
    ListNode* tail = newhead;
    ListNode* cur1 = reverselist1, * cur2 = reverselist2;
    int carry = 0;
    while (cur1 && cur2)
    {
        int sum = cur1->val + cur2->val + carry;
        carry = sum / 10;
        sum = sum % 10;
        ListNode* newnode = new ListNode(sum);
        tail->next = newnode;
        tail = tail->next;
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    while (cur1)
    {
        int sum = cur1->val + carry;
        carry = sum / 10;
        sum = sum % 10;
        ListNode* newnode = new ListNode(sum);
        tail->next = newnode;
        tail = tail->next;
        cur1 = cur1->next;
    }
    if (carry)
    {
        ListNode* newnode = new ListNode(carry);
        tail->next = newnode;
    }
    return reverse(newhead->next);
}

void Print(ListNode* node)
{
    while (node)
    {
        cout << node->val;
        node = node->next;
    }
    cout << endl;
}

int main()
{
    vector<int> nums1{ 9,9,9,9 };
    vector<int> nums2{ 1 };
    ListNode* list1 = createlist(nums1);
    ListNode* list2 = createlist(nums2);
    ListNode* res = Add(list1, list2);
    Print(res);
    return 0;
}

时间复杂度O(N)
空间复杂度O(1)

0 赞同 0 条回复

Laboratory 普通 2024年3月3日下午8:48

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
        /**
         * 反转链表
         * @param head
         * @return ListNode
         */
        private ListNode reverse(ListNode head) {
            if(head == null || head.next == null) {
                return head;
            }
            ListNode newHead = reverse(head.next);
            head.next.next = head;
            head.next = null;
            return newHead;
        }

        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // 先反转
            l1 = reverse(l1);
            l2 = reverse(l2);
            int mark = 0; // 标志位
            ListNode newHead = new ListNode(-1);
            ListNode cur = newHead;
            while (l1 != null || l2 != null) {
                int val1 = l1 == null ? 0 : l1.val;
                int val2 = l2 == null ? 0 : l2.val;
                int realVal = 0;
                if(val1 + val2 + mark >= 10) {
                    realVal = val1 + val2 + mark - 10;
                    mark = 1;
                } else {
                    realVal = val1 + val2 + mark;
                    mark = 0;
                }
                cur.next = new ListNode(realVal);
                cur = cur.next;
                if(l1 != null) {
                    l1 = l1.next;
                }
                if(l2 != null) {
                    l2 = l2.next;
                }
            }

            // 最后若标志位为1，则最后一位补1
            if(mark == 1) {
                cur.next = new ListNode(1);
            }
            // 最后再反转
            return reverse(newHead.next);
        }
}

思路见注释，时间复杂度O(n),n为较长链表，空间复杂度，由于反转链表用了栈，空间复杂度为O(n)

0 赞同 0 条回复

是hua不是pua 普通 2024年3月3日下午8:38

public ListNode ListNodeAddition(ListNode headA, ListNode headB){
        ListNode headAR = reverse(headA);
        ListNode headBR = reverse(headB);
        ListNode result = new ListNode(); // 结果采用头插法
        int a = 0;
        while(headAR != null && headBR != null){
            int sum = headAR.val + headBR.val + a;
            int val =sum % 10;
            a = sum / 10;
            ListNode node = new ListNode(val);
            node.next = result.next;
            result.next = node;
            headAR = headAR.next;
            headBR = headBR.next;
        }
        if(headBR != null){
            headAR = headBR;
        }
        while(headAR != null){
            int sum = headAR.val + a;
            int val =sum % 10;
            a = sum / 10;
            ListNode node = new ListNode(val);
            node.next = result.next;
            result.next = node;
            headAR = headAR.next;
        }
        return result.next;
    }

    public ListNode reverse(ListNode head){
        ListNode head1 = new ListNode();
        while(head != null){
            ListNode next = head.next;
            head.next = head1.next;
            head1.next = head;
            head = next;
        }
        return head1.next;
    }

链表常用思路头插法

0 赞同 0 条回复

【链表专题】字节真题：单链表相加

代码参考

共以下 43 个回答

代码

第一版：杂乱

# 回答此问题取消回复

【链表专题】字节真题：单链表相加

代码参考

共以下 43 个回答

代码

第一版：杂乱

# 回答此问题 取消回复

# 回答此问题取消回复