链表相加(二)_

C/C++

牛客131756360号

为什么最后一个案例通过不了，好迷呀，求指导~
class Solution {
private:
stack<int>stack1;
stack<int>stack2;
public:
ListNode* addInList(ListNode* head1, ListNode* head2) {
// write code here
//分别将两个链表的值存放在两个栈中
while(head1||head2){
if(head1){
stack1.push(head1->val);
head1=head1->next;
}
if(head2){
stack2.push(head2->val);
head2=head2->next;
}
}
ListNode* newhead=new ListNode(-1);//创建新链表的头结点
int carry=0;//用来存储进位
while(!stack1.empty()||!stack1.empty()||carry!=0){
int a=0;
int b=0;
if(!stack1.empty()){
a=stack1.top();
stack1.pop();
}
if(!stack2.empty()){
b=stack2.top();
stack2.pop();
}
int sum=a+b+carry;//计算相加的数值
int num=sum%10;//当前的数为除以10的余数
carry=sum/10;//进位等于当前的数字除以10的余数
ListNode* cur=new ListNode(-1);//创建一个存放当前数字的新节点
cur->val=num;
cur->next=newhead->next;//并讲结点存放在头结点的后面
newhead->next=cur;
}
return newhead->next;//注意，这里输出的是newhead->next;因为newhead是头结点，不存放信息
}
};

发表于 2022-03-24 15:18:52 回复(0)

Go

咕噜咕噜崩

func addInList( head1 *ListNode ,  head2 *ListNode ) *ListNode {
    // write code here
    head1 = recover(head1)
    head2 = recover(head2)
    var res *ListNode
    var more int
    for head1 != nil || head2 != nil || more > 0 {
        var sum int
        if head1 != nil {
            sum += head1.Val
            head1 = head1.Next
        }
        if head2 != nil {
            sum += head2.Val
            head2 = head2.Next
        }
        res = &ListNode{
            Val: (sum+more)%10,
            Next: res,
        }
        more = (sum+more)/10
    }
    return res
}

func  recover(head *ListNode) *ListNode {
    var pre *ListNode
    var next *ListNode
    for head != nil {
        next = head.Next
        head.Next = pre
        pre = head
        head = next
    }
    return pre
}

发表于 2021-12-20 22:49:56 回复(0)

C++

木析

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* reverse(ListNode* head) {
        if(head==nullptr || head->next==nullptr)
            return head;
        ListNode *a=nullptr, *b=head, *c=head->next;
        while(c!=nullptr) {
            b->next=a;
            a=b;
            b=c;
            c=c->next;
        }
        b->next=a;
        return b;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        ListNode* A=reverse(head1); //反转链表
        ListNode* B=reverse(head2); //反转链表
        ListNode* a=A, *b=B;
        int sum=0;
        ListNode* res=new ListNode(0);
        ListNode* cur=res;
        while(a!=nullptr || b!=nullptr || sum>0) {
            if(a!=nullptr) {
                sum+=a->val;
                a=a->next;
            }
            if(b!=nullptr) {
                sum+=b->val;
                b=b->next;
            }
            cur->next=new ListNode(sum%10);
            sum/=10;
            cur=cur->next;
        }
        cur=reverse(res->next);
        //释放额外空间
        delete res;
        //复原现场
        head1=reverse(head1);
        head2=reverse(head2);
        return cur;
    }
};

发表于 2021-09-14 19:36:20 回复(0)

Java

tysb

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        Stack<Integer> res = new Stack<>();
        while(head1 != null) {
            s1.push(head1.val);
            head1 = head1.next;
        }
        while (head2 != null) {
            s2.push(head2.val);
            head2 = head2.next;
        }
        int add = 0;
        while(!s1.isEmpty() && !s2.isEmpty()) {
            int temp = add + s1.pop() + s2.pop();
            if (temp > 9) {
                add = 1;
                res.push(temp - 10);
            } else {
                add = 0;
                res.push(temp);
            }
        }
        if (!s2.isEmpty()) {
            while(!s2.isEmpty() && add == 1) {
                int temp = s2.pop() + add;
                if (temp > 9) {
                    res.push(0);
                } else {
                    add = 0;
                    res.push(temp);
                }
            }
            while(!s2.isEmpty()) {
                res.push(s2.pop());
            }
        }
        if (!s1.isEmpty()) {
            while(!s1.isEmpty() && add == 1) {
                int temp = s1.pop() + add;
                if (temp > 9) {
                    res.push(0);
                } else {
                    add = 0;
                    res.push(temp);
                }
            }
            while(!s1.isEmpty()) {
                res.push(s1.pop());
            }            
        }
        if (add == 1) {
            res.push(1);
        }
        ListNode head = new ListNode(res.pop());
        ListNode node = head;
        while(!res.isEmpty()) {
            node.next = new ListNode(res.pop());
            node = node.next;
        }
        return head;
    }
}

发表于 2021-08-25 20:37:30 回复(0)

C/C++

我爱吃果冻

1.翻转两个链表，让head2,ret2始终指向较长的链表
2.处理较短的链表的相加和，
3.然后处理进位
4.翻转链表
4.最后看是否需要开辟新的节点，需要则直接插入到链表头部

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    // 翻转链表
    ListNode* reverse(ListNode* head1, int& len1) {
        ListNode* ret1 = new ListNode(-1);
        ret1->next = NULL;
        while(head1) {
            len1++;
            ListNode* t = head1;
            head1 = head1->next;
            t->next = ret1->next;
            ret1->next = t;
        }
        return ret1->next;
    }
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        // 反转一次
        int len1 = 0, len2 = 0;
        ListNode* ret1 = new ListNode(-1);
        ListNode* ret2 = new ListNode(-1);
        ret1->next = reverse(head1, len1);
        ret2->next = reverse(head2, len2);
        if (len1 <= len2) { // head2 指向比较长的地方
            head1 = ret1->next; head2 = ret2->next;
        } else {
            head1 = ret2->next; head2 = ret1->next;
            ret2->next = head2; //ret2 也始终指向长的链表
        }
        int len = min(len1, len2);
        int num = 0;
        while(len--) { // 处理相加的操作
            head2->val += (head1->val + num);
            num = head2->val / 10;
            head2->val %=  10;
            head2 = head2->next;
            head1 = head1->next;
        }
        while(num != 0 && head2) { // 需要再次进位的操作
            head2->val += num;
            num = head2->val / 10;
            head2->val %= 10;
            head2 = head2->next;
        }
        ret2->next = reverse(ret2->next, len); //翻转已经处理好的所有节点
        if (head2 == NULL && num != 0) { // 需要开辟新的节点的时候，创建好直接插入头部
            ListNode* new_node = new ListNode(num);
            new_node->next = ret2->next;
            ret2->next = new_node;
        }
        return ret2->next;
    }
};

发表于 2020-12-21 19:24:30 回复(0)

C/C++

ぎんいろひこうせん

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* reverseLinkList(ListNode* head){
        ListNode* cur = head, *pre=NULL, *temp = NULL;
        while(cur){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* head3 = reverseLinkList(head1);
        ListNode* head4 = reverseLinkList(head2);
        int count = 0;
        ListNode* dummy = new ListNode(0);
        ListNode* res = dummy;
        while(head3||head4||count){
            if(head3){
                count += head3->val;
                head3 = head3->next;
            }
            if(head4){
                count += head4->val;
                head4 = head4->next;
            }
            res->next = new ListNode(count%10);
            count = count/10;
            res = res->next;
        }
        ListNode* ans = reverseLinkList(dummy->next);
        return ans;
        
    }
};

发表于 2020-10-12 16:49:36 回复(0)

Game7

//写的过于复杂了，但是能AC
class Solution {
public:
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    int add=0;
    ListNode *last;
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        int size1=0,size2=0;
        ListNode *tmp1=head1,*tmp2=head2;
        while(tmp1){
            tmp1=tmp1->next;
            ++size1;
        }
        while(tmp2){
            tmp2=tmp2->next;
            ++size2;
        }
        if(size1<size2)    swap(head1,head2);
        int dif=abs(size1-size2);
        ListNode *node=new ListNode(0);
        ListNode *res=node;
        for(int i=0;i<dif-1;i++){
            ListNode* tmp=new ListNode(0);
            node->next=tmp;
            node=tmp;
        }
        node->next=head2;
        head2=res;
        head1=reverseList(head1);
        head2=reverseList(head2);
        ListNode *ans=listAdd(head1,head2);
        if(add) last->next=new ListNode(1);
        return reverseList(ans);
    }
    ListNode* reverseList(ListNode *root){
        if(root==NULL)    return root;
        ListNode *slow=new ListNode(root->val),*fast=root;
        root=root->next;
        while(root){
            fast=root;
            root=root->next;
            fast->next=slow;
            slow=fast;
        }
        return slow;
    }
    ListNode* listAdd(ListNode* head1,ListNode* head2){
        ListNode *ans=head1;
        while(head1&&head2){
            int tmp=(head1->val+head2->val+add)%10;
            add=(head1->val+head2->val+add)>9?1:0;
            head1->val=tmp;
            if(head1->next==nullptr)    last=head1;
            head1=head1->next;
            head2=head2->next;
        }
        return ans;
    }
};

编辑于 2020-09-08 22:17:15 回复(0)

Java

牛客817314536号

import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
ListNode head3=new ListNode(1);
ListNode pre=new ListNode(1);
ListNode head3temp=new ListNode(1);
head3temp=head3;
Stack<Integer> s1=new Stack<Integer>();
Stack<Integer> s2=new Stack<Integer>();
Stack<Integer> s3=new Stack<Integer>();
int b=0;
int val=0;
while(head1!=null)
{
s1.push(head1.val);
head1=head1.next;
}
while(head2!=null)
{
s2.push(head2.val);
head2=head2.next;
}
while(!s1.isEmpty()&&!s2.isEmpty())
{
val=s1.pop()+s2.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s1.isEmpty())
{
val=s1.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s2.isEmpty())
{
val=s2.pop()+b;
if(val>=10)
{
val=val-10;
b=1;
}
else
b=0;
s3.push(val);
}
while(!s3.isEmpty())
{
head3.val=s3.pop();
head3.next=new ListNode(0);
pre=head3;
head3=head3.next;
}
pre.next=null;
return head3temp;
}
}

发表于 2021-09-09 20:57:21 回复(0)

mikufansye

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1==null) return head2;
        if(head2==null) return head1;
        ListNode l1=reverse(head1);
        ListNode l2=reverse(head2);
        ListNode result=new ListNode(0);
        int c=0;
        while(l1!=null||l2!=null||c!=0)
        {
            int v1=l1!=null?l1.val:0;
            int v2=l2!=null?l2.val:0;
            int val=v1+v2+c;
            c=val/10;
            ListNode cur=new ListNode(val%10);
            cur.next=result.next;
            result.next=cur;
            if(l1!=null)
                l1=l1.next;
            if(l2!=null)
                l2=l2.next;
        }
        return result.next;  
    }
    
    public ListNode reverse(ListNode node)
    {
        if(node==null) return node;
        ListNode pre=null,next=null;
        while(node!=null)
        {
            next=node.next;
            node.next=pre;
            pre=node;
            node=next;
        }
        return pre;
    }
    
}

java没有答案原来是java都过不掉只能过过75%

发表于 2020-08-29 16:41:25 回复(8)

C/C++

流浪剑士

从链表尾部开始相加，可以利用栈的性质

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        if(head1 == NULL)
        {
            return head2;
        }
        if(head2 == NULL)
        {
            return head1;
        }
        
        stack<ListNode *> s1;
        stack<ListNode *> s2;
        while(head1 != NULL)
        {
            s1.push(head1);
            head1 = head1->next;
        }
        while(head2 != NULL)
        {
            s2.push(head2);
            head2 = head2->next;
        }
        int subsum = 0;
        while(!s1.empty()||!s2.empty())
        {
            int sum = subsum;
            if(!s1.empty())
            {
                sum += s1.top()->val;
                head1 = s1.top();
                s1.pop();
            }
            if(!s2.empty())
            {
                sum += s2.top()->val;
                if(s2.size()>s1.size())
                {
                    head1 = s2.top();
                }
                s2.pop();
            }
            if(sum < 10)
            {
                subsum = 0;
                head1->val = sum;
            }
            else
            {
                subsum = sum/10;
                head1->val = sum%10;
            }
        }
        if(subsum > 0)
        {
            head2 = new ListNode(subsum);
            head2->next = head1;
            return head2;
        }
        
        return head1;
    }
};

发表于 2020-08-26 16:27:08 回复(4)

C++

空中转体一周半

写一个比较容易让人看懂的解法：

1.链表从个位数加起，因此首先把两个链表逆序。

2.调整链表位数不齐，把两个链表的长度调整一致，短链表后面补0。

3.进行相加，设置一个下一位进位，每当当前位数超过10，设置进位为1，进位位参与运算过后立即置0。

4.将相加后的链表结果逆序返回。

运行结果：97% 88%

class Solution {
public:

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        //1.逆序两个链表
        ListNode* h1 = reverse(head1);
        ListNode* h2 = reverse(head2);
        //2.链表对齐补零
        addZero(h1,h2);
        //3.设置进位为并且相加
        int nextAdd=0;
        ListNode* head = h1;
        int temp;
        while(h1->next){
            temp = h1->val+h2->val+nextAdd;//当前位就是两个链表的每一位与进位位相加
            if(nextAdd==1)nextAdd=0;//进位位参与运算后置零
            if(temp>=10){
                h1->val=temp%10;//产生进位
                nextAdd=1;
            }
            else h1->val = temp;
            h1=h1->next;
            h2=h2->next;
        }
        //最后一位单独运算，因为要考虑结果是否超过最大位数，超过最大位数，要新建链表扩容
         temp = h1->val+h2->val+nextAdd;
        if(temp>=10){
            h1->val = temp%10;
            h1->next = (ListNode*)malloc(sizeof(ListNode));
            h1->next->val=1;
            h1->next->next=NULL;
        }
        else h1->val=h1->val+h2->val+nextAdd;
        return reverse(head);
    }
    void addZero(ListNode *h1,ListNode *h2){
        while(h1->next&&h2->next){
            h1=h1->next;
            h2=h2->next;
        }
        //以下两个if只有一个会执行，短的补零
        if(h1->next){
            while(h1->next){
               h2->next=(ListNode*)malloc(sizeof(ListNode));
               h2->next->next=NULL;
               h2->next->val=0;
               h2=h2->next;
               h1=h1->next;
            }
        }
        if(h2->next){
            while(h2->next){
               h1->next=(ListNode*)malloc(sizeof(ListNode));
               h1->next->next=NULL;
               h1->next->val=0;
               h1=h1->next;
               h2=h2->next;
            }
        }
    }
    //链表逆序
    ListNode * reverse(ListNode * list){
        if(!list||!list->next)return list;
        ListNode * p=list;
        ListNode *head = list;
        list=list->next;
        p->next=NULL;
        while(list){
            head = list;
            list=list->next;
            head->next=p;
            p=head;
        }
        return p;
    }
};

发表于 2021-09-11 11:22:03 回复(1)

Bourne_

class Solution {
public:

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        ListNode* newh1=nullptr;
        ListNode* newh2=nullptr;
        ListNode* p1=head1;
        ListNode* p2=head2;
        int len1=0,len2=0;
//翻转链表p1,p2，并记录链表长度
        while(p1)
        {
            p1=head1->next;
            head1->next=newh1;
            newh1=head1;
            head1=p1;
            len1++;
        }
        while(p2)
        {
            p2=head2->next;
            head2->next=newh2;
            newh2=head2;
            head2=p2;
            len2++;
        }
//令head1为长链表，后面相加结果直接在head1上改
        if(len1<len2)
        {
            head1=newh2;
            head2=newh1;
        }
        else
        {
            head1=newh1;
            head2=newh2;
        }
        int carry=0;
        p1=head1,p2=head2;
        while(1)
        {
//链表相加，短链表结束break
            plus(p1,p2,carry);
            if(!p2->next)
            {
                break;
            }
            p1=p1->next;
            p2=p2->next;
        }
//短链表的值已经全部计算过，注意将短链表的值置零（未置零出错过）
        p2->val=0;
//还有进位就继续在长链表上相加，没进位长链表的值就不用修改了，直接返回长链表的头结点，省去了后面的无意义相加（比如长链表长度10000，短链表长度1，这样只用相加一两次）
        while(carry)
        {
            if(!p1->next)
            {
                p1->next=new ListNode(1);
                carry=0;
            }
            else
            {
                p1=p1->next;
                plus(p1,p2,carry);
            }
        }
//将长链表翻转过来就是结果
        p1=head1,newh1=nullptr;
        while(p1)
        {
            p1=head1->next;
            head1->next=newh1;
            newh1=head1;
            head1=p1;
        }
        return newh1;
    }
//节点相加
    void plus(ListNode* &p1, ListNode* &p2,int &carry)
    {
         p1->val=p1->val+p2->val+carry;
         if(p1->val>9)
         {
            p1->val%=10;
            carry=1;
         }
          else carry=0;
    }
};

编辑于 2020-09-01 08:48:32 回复(0)

Python3

kkkkcui

1先将链表分别存入栈中

2再从栈的末尾开始相加，记录进位值和当前结果

3使用头插法将结果存入结果链表中

class Solution:
    def addInList(self, head1, head2):
        # write code here
        if head1 == None:
            return head2
        if head2 == None:
            return head1
        
        '''存入栈'''
        s1, s2 = [], []
        while head1:
            s1.append(head1.val)
            head1 = head1.next
        while head2:
            s2.append(head2.val)
            head2 = head2.next
        
        '''每次从栈末尾取出一个数进行相加，记录进位值并更新输出结果'''
        i = 0  # 进位值
        temp = ListNode(0) # 链表尾部
        while len(s1)>0 and len(s2)>0:
            num1 = int(s1.pop())
            num2 = int(s2.pop())
            node = ListNode((num1 + num2 + i)%10) # 当前结果
            i = (num1 + num2 + i)//10 # 更新进位值
            node.next = temp.next # 头插法，将新生成的数插入到当前链表的头部
            temp.next = node
        
        '''处理其余特殊情况：s1先为空、s2先为空'''
        while len(s1)>0:
            num = int(s1.pop())
            node = ListNode((num + i)%10)
            i = (num + i)//10
            node.next = temp.next 
            temp.next = node
            
        while len(s2)>0:
            num = int(s2.pop())
            node = ListNode((num + i)%10)
            i = (num + i)//10
            node.next = temp.next
            temp.next = node
            
        return temp.next

发表于 2021-07-24 14:32:08 回复(6)

好好学习11&面向简历编程

使用栈逆序链表节点，然后使用头插法。

import java.util.*;
public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        Stack<ListNode> stack1=new Stack<>();
        Stack<ListNode> stack2=new Stack<>();
        ListNode p1=head1;
        ListNode p2=head2;
        while(p1!=null){
            stack1.push(p1);
            p1=p1.next;
        }
        while(p2!=null){
            stack2.push(p2);
            p2=p2.next;
        }
        int cause=0;
        ListNode dummy=new ListNode(0);
        ListNode p=dummy;
        while(!stack1.isEmpty()||!stack2.isEmpty()){
            int pp1=!stack1.isEmpty()?stack1.pop().val:0;
            int pp2=!stack2.isEmpty()?stack2.pop().val:0;
            int plus=cause+pp2+pp1;
            cause=plus/10;
            ListNode newNode=new ListNode(plus%10);
            newNode.next=p.next;
            p.next=newNode;
        }
        return dummy.next;
    }
}

发表于 2020-10-31 14:41:33 回复(3)

Java

624huiguorou

链表相加

只有链表顺序是从个位开始，最高位结束时才可以相加（记录本位和进位，最后一位进位再新建一个节点即可）。如果链表顺序不是这样，则需要反转。

顺序不是从个位数开始，所以反转，然后加，然后结果再反转得到最后结果。

当p1或p2到头时候，就只加另一个。

进位c需要在里面加。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        //先反转，然后再求和
        ListNode p1 = reverse(head1);
        ListNode p2 = reverse(head2);
        //c为进位，a为当前位
        ListNode root = new ListNode(-1), t;
        t = root;
        int c = 0, a = 0;
        //p1和p2都不能为null
        while(p1 != null && p2 != null){
            //需要在里面加c
            a = (p1.val + p2.val + c) % 10;
            c = (p1.val + p2.val + c) / 10;
            t.next = new ListNode(a);
            t = t.next;
            p1 = p1.next;
            p2 = p2.next;
        }
        //分为一个为空，一个不为空（两种），两个都为空
        while(p1 != null){
            //需要在里面加c
            a = (p1.val + c) % 10;
            c = (p1.val + c) / 10;
            t.next = new ListNode(a);
            t = t.next;
            p1 = p1.next;
        }
        while(p2 != null){
            //需要在里面加c
            a = (p2.val + c) % 10;
            c = (p2.val + c) / 10;
            t.next = new ListNode(a);
            t = t.next;
            p2 = p2.next;
        }
        if(c == 1){
            t.next = new ListNode(1);
        }
        ListNode r = reverse(root.next);
        return r;
    }
    
    public ListNode reverse(ListNode head){
        ListNode a = head, c = null, b;
        while(a != null){
            b = a.next;
            a.next = c;
            c = a;
            a = b;
        }
        return c;
    }
}

发表于 2022-07-19 14:37:25 回复(0)

Java

TylerChen

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode res = new ListNode(-1), p = res;
        int add = 0;//进位
        while(head1 != null || head2 != null){
            int a = head1 != null ? head1.val : 0;
            int b = head2 != null ? head2.val : 0;
            int re = add + a + b;
            add = re >= 10 ? 1 : 0;
            p.next = new ListNode(re % 10);
            p = p.next;
            if(head1 != null){
                head1 = head1.next;
            }
            if(head2 != null){
                head2 = head2.next;
            }
        }
        if(add != 0){
            p.next = new ListNode(1);
        }
        return reverse(res.next);
    }
    ListNode reverse(ListNode head){
        ListNode newHead = null;
        ListNode p = head;
        while(p != null){
            ListNode next = p.next;
            p.next = newHead;
            newHead = p;
            p = next;
        }
        return newHead;
    }
}

发表于 2021-08-08 19:45:49 回复(0)

牛客69143547号

//先反转链表，然后正常带进位的链表加法，最后把结果再反转
class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        ListNode* l1=reverse(head1);
        ListNode* l2=reverse(head2);
        int cur=0;
        ListNode* head=new ListNode(-1);
        ListNode* temp=head;
        while(l1||l2||cur)
        {
            if(l1)
            {
                cur+=l1->val;
                l1=l1->next;
            }
            if(l2)
            {
                cur+=l2->val;
                l2=l2->next;
            }
            ListNode* t=new ListNode(cur%10);
            temp->next=t;
            temp=temp->next;
            cur/=10;
        }
        temp->next=nullptr;
        ListNode* ans=head->next;
        return reverse(ans);
    }
    ListNode* reverse(ListNode* head)  //反转链表
    {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur!=nullptr)
        {
            ListNode* next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

发表于 2021-01-10 23:26:50 回复(0)

Tony11111

同样的思路 C+能过 python就不行。。。

发表于 2020-08-28 17:41:50 回复(2)

dreamerlzl

Python，卡75%

发表于 2020-08-28 00:05:44 回复(1)

C

划船全靠浪呀

一种比较传统的做法

typedef struct ListNode* pnode;

// 将两个链表的值求和
void mycombine(pnode head1,pnode head2,int len1,int len2){
    pnode p=head1;
    pnode q=head2;
    while(len1>len2){
        p=p->next;
        len1--;
    }//保持后对齐
    while(p){
        p->val+=q->val;
        p=p->next;
        q=q->next;
    }
}

int carrybit(pnode head){  //实现进位操作
    if(head==NULL)return 0;
    head->val+=carrybit(head->next);
    if(head->val>=10){
        head->val-=10;
        return 1;
    }else return 0;
}

int mystrlen(pnode head){//计算链表得长度 
    int count=0;
    while(head){
        head=head->next;
        count++;
    }
    return count;
} 

struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {
    if(head1==NULL) return head1;
    if(head2==NULL) return head2;
    int len1=mystrlen(head1);
    int len2=mystrlen(head2);
    pnode temp=NULL;
    //找到较大的链表，求和得到的放入其中；
    if(len1>=len2){
        temp=head1;
        mycombine(temp,head2,len1,len2);//两个链表的值加到temp里
    }else{
        temp=head2;
        mycombine(temp,head1,len2,len1);//两个链表的值加到temp里
    }
    int i=carrybit(temp);
    if(i==1){
        pnode newhead=(pnode)malloc(sizeof(struct ListNode));
        newhead->val=1;
        newhead->next=temp;
        temp=newhead;
    }
    return temp;
}

发表于 2022-11-25 23:09:02 回复(0)

链表相加(二)

输入

输出

说明

输入

输出

备注:

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题