招舟子普通 2023年8月25日上午12:15

思路先反转再相加

0 赞同 0 条回复

mpweixin用户普通 2023年7月19日下午11:09

/**
* 反转链表 – 递归实现
* @param head
* @return
*/
public LinkNode reverseList(LinkNode head){
if(head null || head.next null){
return head;
}
LinkNode tmp = reverseList(head.next);
head.next.next = head;
head.next = null;
return tmp;
}
/**
* 单链表相加-不允许使用栈，队列
* 先将两链表反转后按位相加，然后再反转
* @param headA
* @param headB
* @return
*/

public LinkNode addTwoList(LinkNode headA, LinkNode headB) {
    //虚拟头节点
    LinkNode headV = new LinkNode(0);
    LinkNode cur = headV;
    int sum = 0;
    while (headA != null || headB != null || sum != 0){
        //判断A链表是否还有节点可以加
        if(headA == null){
            sum += headA.val;
            headA = headA.next;
        }
        //判断B链表是否还有节点可以加
        if(headB == null){
            sum += headB.val;
            headB = headB.next;
        }
        cur.next = new LinkNode(sum % 10);
        sum = sum / 10;
        cur = cur.next;
    }
    return reverseList(headV).next;

}

0 赞同 0 条回复

ZJS 永久会员 2023年7月15日下午4:38

思路：反转链表
时间复杂度：O(n + m)
空间复杂度：O(1)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // 先判空
        if(head1 == null){
            return head2;
        }
        if(head2 == null){
            return head1;
        }

        // 反转链表
        head1 = recu(head1);
        head2 = recu(head2);

        // 虚拟链表
        ListNode res = new ListNode(-1);
        ListNode p = res;

        // 记录进位
        int temp = 0;

        while(head1 != null || head2  != null){
            int val = temp;

            if(head1 != null){
                val += head1.val;
                head1 = head1.next;
            }

            if(head2 != null){
                val += head2.val;
                head2 = head2.next;
            }

            p.next = new ListNode(val % 10);
            p = p.next;
            temp = val / 10;
        }

        // 如果进位不等于0还需加上
        if(temp > 0){
            p.next = new ListNode(temp);
        }

        return recu(res.next);
    }

    // 递归将head链表反转
    public ListNode recu(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode last = recu(head.next);

        head.next.next = head;
        head.next = null;

        return last;
    }


}

0 赞同 0 条回复

mpweixin用户普通 2023年7月10日上午10:56

class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
 }


public class addListNode{

public static void main(String[] args) {
    ListNode node11 = new ListNode(1);
    ListNode node12 = new ListNode(3);
    ListNode node13 = new ListNode(8);
    ListNode node14 = new ListNode(9);
    ListNode node15 = new ListNode(1);
    node11.next = node12;
    node12.next = node13;
    node13.next = node14;
    node14.next = node15;

<pre><code>ListNode node21 = new ListNode(7);
ListNode node22 = new ListNode(9);
ListNode node23 = new ListNode(9);
node21.next = node22;
node22.next = node23;

ListNode node = ListNodeadd(reverse(node11), reverse(node21));
node = reverse(node);
while(node!=null){
    System.out.print(node.val+"->");
    node = node.next;
}
</code></pre>

}

public  static ListNode reverse(ListNode node){
    ListNode pre = null;
    ListNode temp = null;
    while(node!=null){
        temp = node.next;
        node.next = pre;
        pre = node;
        node = temp;
    }
    return pre;
}

public static ListNode ListNodeadd(ListNode node1,ListNode node2){
    ListNode retNode = new ListNode(0);
    ListNode temp = retNode;
    int sum = 0;
    while(node1 != null || node2 != null || sum != 0){
        if(node1 != null){
            sum += node1.val;
            node1 = node1.next;
        }
        if(node2 != null){
            sum += node2.val;
            node2 = node2.next;
        }
        temp.next = new ListNode(sum % 10);
        sum  = sum / 10;
        temp = temp.next;

<pre><code>}
return retNode.next;

}
思路：反转链表+两数相加
}

0 赞同 0 条回复

淡色花樱普通 2023年7月9日上午10:50

“`java
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 heard1,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 条回复

cute. 普通 2023年7月7日上午11:37

思路：反转链表+两数相加

var reverseList = function (head) {
    let pre = null;
    let cur = head;
    while (cur) {
        let nxt = cur.next;
        cur.next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
};

var addTwo = function (l1, l2) {
    let dummy = new ListNode(); // 哨兵节点
    let cur = dummy;
    let carry = 0; // 进位
    while (l1 || l2 || carry) {
        if (l1) carry += l1.val; // 节点值和进位加在一起
        if (l2) carry += l2.val; // 节点值和进位加在一起
        cur = cur.next = new ListNode(carry % 10); // 每个节点保存一个数位
        carry = Math.floor(carry / 10); // 新的进位
        if (l1) l1 = l1.next; // 下一个节点
        if (l2) l2 = l2.next; // 下一个节点
    }
    return dummy.next; // 哨兵节点的下一个节点就是头节点
};

var addTwoNumbers = function (l1, l2) {
    l1 = reverseList(l1);
    l2 = reverseList(l2);
    let l3 = addTwo(l1, l2);
    return reverseList(l3);
}

0 赞同 0 条回复

Gracelyne 普通 2023年7月6日下午12:24

“`cpp 运用翻转链表，先翻转，再相加，用temp记录进位改变cur节点的val和next，最后翻转
class Node {
public:
int val;
Node* next;

Node(int _val) {
    val = _val;
    next = NULL;
}

};

class Solution {
public:
Node* reverseList(Node* head){
//reverse
Node *prev, *next = NULL;
Node *cur = head;
while(cur != nullptr){
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
head = prev;
return head;
}

Node* singleLinkAdd(Node* first, Node* second){
    Node *rev1 = reverseList(first);
    Node *rev2 = reverseList(second);
    Node *dummy = new Node(-1);
    Node *cur = rev1;
    int temp, val = 0;
    while(rev1 != nullptr || rev2 != nullptr){
        // Node *next = new Node();
        int sum = rev1->val + rev2->val + temp;
        val = sum>=10 ? 9 ：sum % 9;
        if(rev1 == nullptr){
            cur->next = rev2;
        } else if (rev2 == nullptr){
            cur->next = rev1;
        }
        cur->val = val;
        temp = sum>=10 ? sum % 9 : 0;
        cur = cur->next;
    }
    Node *res = reverseList(rev1);
    return res;
}

};

“`

0 赞同 0 条回复

BOZ 普通 2023年7月4日下午2:15

写了一个辅助函数对input链表进行反转，而后从最后一位开始进位相加，设置一bool变量标记进位

class Solution {
public:
    void reverseList(ListNode* head) {
        assert(head != nullptr);
        // printList(head);
        ListNode* curr = head->next;
        head->next = nullptr;
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = head->next;
            head->next = curr;
            curr = next;
        }
        // printList(head);
    }
    ListNode* addup(ListNode* a, ListNode* b) {
        // reverse two list first
        reverseList(a); a = a->next;
        reverseList(b); b = b->next;

        // add up
        ListNode *sum = new ListNode(0);
        bool carry = false;
        while (a != nullptr || b != nullptr || carry) {
            // calculate the current place value
            int p = (carry);
            if (a != nullptr) {p += a->val; a = a->next;}
            if (b != nullptr) {p += b->val; b = b->next;}
            if (p > 9) {carry = true; p -= 10;}
            else carry = false;
            assert(p >= 0 && p <= 9);
            // append sum list
            ListNode *node = new ListNode(p);
            node->next = sum->next;
            sum->next = node;
            // printf("add node %d\n", p);
        }
        return sum;
    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月3日上午10:00

先进行链表得反转，然后从反转后得头节点开始依次进行＋的操作，若大于十则通过一个变量add进行进位的储存，最后要注意的就是，计算到结尾的时候，add可能不为0，此时就要再创建一个节点来储存add的值

package playOffer;

import java.util.Scanner;

class Node{
    public Node(int val){
        this.val=val;
    }
    public int val;
    public Node next;
}
public class Day3 {
    public static Node toInt(int a){
        Node arr=new Node(a%10);
        Node ans=arr;
        a/=10;
        while(a>0){
            arr.next=new Node(a%10);
            a/=10;
            arr=arr.next;
        }
        arr.next=null;
        return ans;
    }
    public static Node toFan(Node head){
        if(head==null ||head.next==null)return head;

        Node b=toFan(head.next);
        head.next.next=head;
        head.next=null;

        return b;

    }
    public static Node addNum(Node a,Node b){
        a=toFan(a);
        b=toFan(b);

        Node ans=new Node(0);
        Node cur=ans;
        int add=0;
        while(a!=null||b!=null){
            int numa=a==null?0:a.val;
            int numb=b==null?0:b.val;
            int sum=numa+numb+add;
//            System.out.println(sum);
            ans.next=new Node(sum%10);
            add=sum/10;
            ans=ans.next;
            if(a!=null)a=a.next;
            if(b!=null)b=b.next;
        }
        if(add>0){
            ans.next=new Node(add);
            ans=ans.next;
        }
        ans.next=null;
        return cur.next;
    }
    public static void show(Node a){
        if(a==null){
            System.out.println("null");
            return;
        }
        while(a!=null){
            System.out.print(a.val+" ");
            a=a.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
//        Scanner sc =new Scanner(System.in);
//        int a=sc.nextInt();
//        Node A=toInt(a);
//        A= toFan(A);
//        int b=sc.nextInt();
//        Node B = toInt(b);
//        B = toFan(B);
//
//
////        A=addNum(A,B);
//        A= toFan(addNum(A,B));
//        while(A!=null){
//            System.out.print(A.val+" ");
//            A=A.next;
//        }



//        System.out.print(count);




    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月30日下午8:04

java
class Solution {
    public Node combineList(Node head1, Node head2) {
        Node head1_new = reverseList(head1);
        Node head2_new = reverseList(head2);
        Node headNew = new Node(0); //建立新链表的头结点
        Node tmp = headNew;
        tmp.next = null; //当两个链表都为空时，最终返回也为空
        int sum = 0; //储存两个数的相加
        while(head1_new != null || head2_new != null || sum != 0) { //只要sum不等于0就要创建新节点
            if(head1_new != null) {
                sum += head1_new.val;
                head1_new = head1_new.next;
            }
            if(head12new != null) {
                sum += head2_new.val;
                head2_new = head2_new.next;
            }
            tmp.next = new Node(sum % 10);
            sum /= 10;
            tmp = tmp.next;
        }
        Node finalHead = reverseList(headNew.next);
        headNew.next = null;
        return finalHead;
    }

    public Node reverseList(Node head) {
        if(head == null || head.next == null) {
            return null;
        }
        Node cur = head, pre = null;
        Node tmp;
        while(cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

时间复杂度O(n+m), 空间复杂度O（1）

0 赞同 0 条回复

大大普通 2023年6月30日上午10:58

 //1 反转 2 add 虚拟尾节点 3 反转//注意需要删除最后一个节点
反转时为了进位的需求，增加了值为0的节点 
#include<bits/stdc++.h>

using namespace std;

struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
  };

Node* Reverse(Node* head){
    Node* cur=head;
    Node* pre=new Node(0);

    while(cur!=NULL){
        Node* tmp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=tmp;    
        //cout<<pre->val<<" ";      
    }
    return pre; 
}

Node* Add(Node* A,Node* B){//A是参考链表 比较长
    Node* head=A;
    int extra=0,whole=0;
    while(head){
     extra=(head->val+B->val+whole)%10;
     int t=head->val;
     head->val=extra;
     whole=(t+B->val+whole)/10;             
     head=head->next;
     B=B->next;
     if(!B) B=new Node(0);
    }
    return A; 
}
int Num(Node* A){
    Node* head=A;
    int a=0;
    while(head){
        a++;
        head=head->next;
    }
    return a;
}
void Show(Node* A){
    Node* head=A;
    while(head){
        cout<<head->val;
        head=head->next;
    }
    cout<<endl;
}
int main(){
    //两个链表
    Node* A=new Node(4);
    A->next=new Node(2);
    A->next->next=new Node(2);
    Node* B=new Node(9);
        B->next=new Node(9);
    B->next->next=new Node(9);
    B->next->next->next=new Node(9);    
    //solve
        Show(A);
        Show(B);
    A=Reverse(A);
    // Show(A);//
    B=Reverse(B);   
    //Show(B);//
    Node* head=NULL;
    if(Num(A)>Num(B))
    head=Add(A,B);
    else head=Add(B,A);
    head=Reverse(head); 
    Show(head);  
    //删除尾节点  需要知道倒数第二个节点
    Node* cur=head;//倒数第二个节点
    Node* nex=head->next;//最后一个节点
    while(cur){
      if(nex->next==NULL){
        free(nex);
        cur->next=NULL;     
      }
      cur=cur->next;
      nex=nex->next;        
    }
    if(head->val==0)
    head=head->next;
    cout<<"the result is:";
    Show(head); 
    return 0;
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月30日上午9:42

反转相加反转

public class AddTwoListNode {
    public static void main(String[] args) {
        //1->3->8->9->1;
        //      7->9->9;
        //1->4->6->9->0
        Node node11 = new Node(1);
        Node node12 = new Node(3);
        Node node13 = new Node(8);
        Node node14 = new Node(9);
        Node node15 = new Node(1);
        node11.next = node12;
        node12.next = node13;
        node13.next = node14;
        node14.next = node15;

        Node node21 = new Node(7);
        Node node22 = new Node(9);
        Node node23 = new Node(9);
        node21.next = node22;
        node22.next = node23;

        Node node = addTwoListNode(node11, node21);
        print(node);
    }

    public static Node addTwoListNode(Node node11, Node node21){
        if (node11 == null) {
            return node21;
        }
        if (node21 == null) {
            return node21;
        }
        print(node11);
        print(node21);

        Node head1 = reverseNodeList(node11);
        Node head2 = reverseNodeList(node21);
        print(head1);
        print(head2);

        Node head = new Node(0);
        Node res = head;
        int carryVal = 0;
        while(head1!=null || head2 !=null) {
            int val1 = 0;
            if (head1 !=null) {
                val1 = head1.getVal();
                head1 = head1.next;
            }
            int val2 = 0;
            if (head2 !=null) {
                val2 = head2.getVal();
                head2 = head2.next;
            }
            int resVal = val1 + val2;
            res.next  = new Node(resVal%10 + carryVal);
            res = res.next;
            carryVal = resVal >= 10 ? 1:0;
        }

        Node node = reverseNodeList(head.next);

        return  node;
    }

    public static Node reverseNodeList(Node head){
        if(head == null) {
            return null;
        }
        //1->3->8->9->1;
        Node pre = null;
        Node cur = head;
        while(cur != null) {
            Node temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public static void print(Node head) {
        System.out.println("==============");
        Node tmp = head;
        while (tmp !=null) {
            System.out.println(tmp.getVal() + "->");
            tmp  = tmp.next;
        }
    }
}

0 赞同 0 条回复

Sexypig. 普通 2023年6月30日上午1:53

代码：

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def twoSum(headA:ListNode,headB:ListNode)->ListNode:
        if not headA or not headB:
            return headA if headA else headB
        def reverseList(head:ListNode)->ListNode:
            if not head or not head.next:
                return head
            pre=None
            cur=head
            nex=head.next
            while nex:
                cur.next=pre
                pre=cur
                cur=nex
                nex=nex.next
            cur.next=pre
            return cur
        headA=reverseList(headA)
        headB=reverseList(headB)
        res:ListNode=None
        flag:bool=False
        cur:ListNode=None
        while headA and headB:
            num=headA.val+headB.val+(1 if flag else 0)
            flag=False
            if num>=10:
                num-=10
                flag=True
            if res is None:
                res=ListNode(num)
                cur=res
            else:
                cur.next=ListNode(num)
                cur=cur.next
            headA,headB=headA.next,headB.next
        headB=headA if headA else headB
        while headB:
            cur.next=ListNode(headB.val)
            headB,cur=headB.next,cur.next
        res=reverseList(res)
        return res

if __name__ == '__main__':
    A:ListNode=ListNode(1)
    cur=A
    for i in range(2,5):
        cur.next=ListNode(i)
        cur=cur.next
    B:ListNode=ListNode(3)
    B.next=ListNode(4)
    res=Solution.twoSum(A,B)
    cur=res
    while cur:
        print(cur.val)
        cur=cur.next

时间：遍历两个链表各两次，O(A+B)
空间：O（1）
先对两链表遍历反转，再遍历加和

0 赞同 0 条回复

泡芙永久会员 2023年6月28日下午9:28

Time: O(N+M)
Space:O(1)

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        // 将两个链表进行反转
        ListNode l1 = reverseList(head1);
        ListNode l2 = reverseList(head2);

        // 单链表相加
        // 定义一个新的链表来装相加的值
        ListNode res = new ListNode(0);
        ListNode tmp = res;
        // 是否需要进位
        int carry = 0;
        while (l1 != null || l2 != null) {
            int val = carry;
            if (l1 != null) {
                val += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                val += l2.val;
                l2 = l2.next;
            }
            carry = val / 10;
            tmp.next = new ListNode(val % 10);
            tmp = tmp.next;
        }

        // 如果 carry != 0，即需要进位，新增一个节点
        if (carry != 0) {
            tmp.next = new ListNode(carry);
        }

        // 把相加链表的值再反转
        return reverseList(res.next);
    }

    // 反转链表
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

这道题与牛客网上的链表相加(二)一样，觉得不好测试的同学可以在上面写，链接放在这里
https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b
另外这道题是正向存放的，如果这道题是反向存放呢？题目链接也放在这里了，有兴趣的同学可以尝试一下 https://www.nowcoder.com/practice/521d83306d964c1188639033eb59621d?tpId=196&tqId=40273&ru=/exam/oj
如果想在力扣上做，这里也有一道类似的：面试题 02.05. 链表求和，但是这道题是反向链表相加
https://leetcode.cn/problems/sum-lists-lcci/

0 赞同 0 条回复

Tang 普通 2023年6月28日下午4:43

/**
class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}
*/

public class Solution {

    /**
     * 列表反转
     * @param head
     */
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode curr = head;
        ListNode prev = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    /**
     * 单链表表示十进制整数，求两个正整数的和。1234+34=1268
     * @param head1
     * @param head2
     * @return
     */
    public ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        // 将两个链表反转
        ListNode listNode1 = reverse(head1);
        ListNode listNode2 = reverse(head2);

        // 单链表相加
        ListNode res = new ListNode(0);
        ListNode tmp = res;
        int carry = 0;
        while (listNode1 != null || listNode2 != null) {
            int val = carry;
            if (listNode1 != null) {
                val += listNode1.val;
                listNode1 = listNode1.next;
            }
            if (listNode2 != null) {
                val += listNode2.val;
                listNode2 = listNode2.next;
            }
            carry = val / 10;
            tmp.next = new ListNode(val % 10);
            tmp = tmp.next;
        }
        if (carry != 0) {
            tmp.next = new ListNode(carry);
        }
        return reverse(res.next);
    }
}

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

0 赞同 0 条回复

小吕普通 2023年6月27日下午2:45

c++实现，先反转然后再相加再反转
ListNode* reverseList(ListNode* list)
{
if(listNULL&&list->nextNULL)return list;
ListNode* pre = NULL;
ListNode* cur = list;
ListNode* temp;
while(cur)
{
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* ll1 = reverseList(l1);
ListNode* ll2 = reverseList(l2);
int carry = 0;
ListNode* asc=NULL;
while(ll1!=NULL||ll2!=NULL||carry!=0)
{
int a = ll1NULL?0:ll1->val;
int b = ll2NULL?0:ll2->val;
if(ll1!=NULL)ll1 = ll1->next;
if(ll2!=NULL)ll2 = ll2->next;
int cur = a+b+carry;
carry = cur/10;
cur %= 10;
auto curNode = new ListNode(cur);
curNode->next = asc;
asc = curNode;
}
return asc;
}

0 赞同 0 条回复

小吕普通 2023年6月27日下午2:45

c++实现，先反转然后再相加再反转
ListNode* reverseList(ListNode* list)
{
if(listNULL&&list->nextNULL)return list;
ListNode* pre = NULL;
ListNode* cur = list;
ListNode* temp;
while(cur)
{
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* ll1 = reverseList(l1);
ListNode* ll2 = reverseList(l2);
int carry = 0;
ListNode* asc=NULL;
while(ll1!=NULL||ll2!=NULL||carry!=0)
{
int a = ll1NULL?0:ll1->val;
int b = ll2NULL?0:ll2->val;
if(ll1!=NULL)ll1 = ll1->next;
if(ll2!=NULL)ll2 = ll2->next;
int cur = a+b+carry;
carry = cur/10;
cur %= 10;
auto curNode = new ListNode(cur);
curNode->next = asc;
asc = curNode;
}
return asc;
}

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月27日下午1:47

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *pre,*cur,*tmp;
    pre=NULL;
    cur=head;
    while(cur){
        tmp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=tmp;
    }
    return pre;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    //两个原链表反转一下
    l1=reverseList(l1);
    l2=reverseList(l2);
    int carry=0;//进位
    int add=0;
    //tmp1、tmp2用来遍历原链表
    struct ListNode *tmp1=l1;
    struct ListNode *tmp2=l2;
    struct ListNode *ans=NULL;
    while(tmp1||tmp2||carry==1){//循环终止条件：tmp1=null&&tmp2=null&&carry=0（三者同时满足）
        //新链表结点
        struct ListNode *new=(struct ListNode *)malloc(sizeof(struct ListNode));
        new->next=ans;

        int a=tmp1==NULL?0:tmp1->val;
        if(tmp1!=NULL)tmp1=tmp1->next;
        int b=tmp2==NULL?0:tmp2->val;
        if(tmp2!=NULL) tmp2=tmp2->next;

        add=a+b+carry;
        carry=add/10;
        new->val=add%10;

        ans=new;
    }
    return ans;
}

0 赞同 0 条回复

HU 普通 2023年6月26日下午7:12


// 首先反转链表
function reverseList(head) {
  // 1. 给出结束条件
  if(head === null || head.next === null) {
    return head;
  }

  // 2. 给出等价式子
  let newList = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newList;
}

// 其次两链表相加
function add(headA, headB) {
  // 先创建虚拟头节点
  let listNode = new ListNode(0);
  let cur = listNode;

  // sum用来存放进位
  let sum = 0;

  while(headA !== null || headB !== null || sum !== 0) {
    if(headA !== null) {
      sum += headA.val;
      headA = headA.next;
    }
    if(headB !== null) {
      sum += headB.val;
      headB = headB.next;
    }
    cur.next = new ListNode(sum % 10);
    sum = sum / 10;
    cur = cur.next;
  }

  // 反转结果链表
  let res = reverseList(listNode.next);

  return listNode.next;
}

时间复杂度：O(A+B)。
空间复杂度：O(1)。

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月26日下午2:46

打卡

// 反转链表
function reverseList(head) {
  if (head == null || head.next == null) {
    return head;
  }

  let temp = reverseList(head.next);
  head.next.next = head;
  head.next = null;

  return temp;
}

function add(headA, headB) {
  let newA = reverseList(headA);
  let newB = reverseList(headB);

  let curA = newA;
  let curB = newB;
  let resultHead = new ListNode(0);
  let curRet = resultHead;
  let num = 0;  //用来保存进位
  while (curA != null && curB != null) {
    let node = new NodeList(0);

    // 相加，大于等于10的进1
    node.val = curA.val + curB.val + num;
    if (node.val > 9) {
      node.val = node.val % 10;
      num = 1;
    }
    curRet.next = node;
    curA = curA.next;
    curB = curB.next;
    curRet = curRet.next;
  }

  //反转结果
  let ret = reverseList(resultHead.next);
  return ret;

}

0 赞同 0 条回复

GGBond 普通 2023年6月25日下午8:53

class Solution {
    
    //反转链表
    public Node reverse(Node head){
        Node pre = head;
        Node back = null;
        while(pre != null){
          Node temp = pre.next;
          pre.next = back;
          back = pre;
          pre = temp;
        }
        return back;
    }

    public Node addListNode(Node head1,Node head2){
        //反转链表
        Node head1 = reverse(head1);
        Node head2 = reverse(head2);
        //返回的新链表
        Node newHead = new Node();
        Node p = newHead;
        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 Node(sum % 10);
            sum = sum / 10;
            p = p.next;
        }
        return newHead.next;
    }
}

0 赞同 0 条回复

屠龙手段普通 2023年6月25日下午8:28

将链表压栈再弹出，设置标识位表示进位
# 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: ListNode, l2: ListNode) -> ListNode:
        l1_lst = self.save_lst(l1)
        l2_lst = self.save_lst(l2)
        flag = 0
        res = []
        while l1_lst or l2_lst:
            a = l1_lst.pop() if l1_lst else 0
            b = l2_lst.pop() if l2_lst else 0
            num = a + b + flag
            val = num % 10
            flag = 1 if (num - 10) >= 0 else 0
            res.append(val)
        if flag:
            res.append(flag)
        head = None
        for i in range(len(res)):
            tmp = ListNode(res[i], head)
            head = tmp
        return head   

    def save_lst(self, head):
        p = head
        lst = []
        while p:
            lst.append(p.val)
            p = p.next
        return lst

0 赞同 0 条回复

～普通 2023年6月25日下午7:41

class AddTwoLists {
public:
// 反转链表
ListNode* reverseList(ListNode* node) {
ListNode* pre = nullptr;
ListNode* temp = nullptr;
while (node != nullptr) {
temp = node->next;
node->next = pre;
pre = node;
node = temp;
}
return pre;
}
ListNode* TwoListsSum(ListNode* list1, ListNode* list2){
// 虚拟头结点
ListNode* dummy = new ListNode(-1);
ListNode* curr = dummy;
// sum 用来求和
int sum = 0;
// curry 用来存进位
int carry = 0;
while (list1 || list2 || carry) {
int sum = (list1 ? list1->val : 0) + (list2 ? list2->val : 0) + carry; // 计算当前位置的和
carry = sum / 10; // 计算进位值
ListNode* newNode = new ListNode(sum % 10); // 创建新节点
curr->next = newNode; // 将新节点连接到结果链表的末尾
curr = curr->next; // 更新当前节点

        if (list1) list1 = list1->next;  // 移动指针到下一节点
        if (list2) list2 = list2->next;  // 移动指针到下一节点
     }

    ListNode* result = dummy->next;  // 获取真正的结果链表
    delete dummy;  // 删除虚拟头结点
    return result;
}

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

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

0 赞同 0 条回复

普通 2023年6月25日上午10:44

public static ListNode addListNode(ListNode l1, ListNode l2) {
        ListNode indexl1 = l1;
        int lengthl1 = 0;
        ListNode indexl2 = l2;
        int lengthl2 = 0;
        while(indexl1 != null){
            indexl1 = indexl1.next;
            lengthl1++;
        }
        while(indexl2 != null){
            indexl2 = indexl2.next;
            lengthl2++;
        }
        indexl1 = l1;
        indexl2 = l2;
        ListNode resultListNode = null;
        int differenceLength = lengthl1 - lengthl2;
        if(differenceLength > 0){
            while(differenceLength>0){
                indexl1 = indexl1.next;
                differenceLength--;
            }
            resultListNode = l1;
        }else{
            differenceLength = differenceLength * -1;
            while(differenceLength>0){
                indexl2 = indexl2.next;
                differenceLength--;
            }
            resultListNode = l2;
        }
        while(indexl1 != null){
            int endNumber = indexl1.val+indexl2.val;
            indexl1.val =endNumber;
            indexl2.val =endNumber;
            indexl1 = indexl1.next;
            indexl2 = indexl2.next;
        }
        return resultListNode;
    }

思路:找出两个链表相差数以及最长链表,将最长链表进位到和短链表一样的长度,两两相加后覆盖原链表值
时间复杂度O(n+m) 空间复杂度O(1)

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月24日上午5:06

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        prev = None
        cur = head

        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        return prev

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        carry = 0
        res = ListNode()
        cur = res

        while l1 or l2:
            cur.next = ListNode()
            cur = cur.next

            cur.val += carry
            carry = 0

            if l1 and l2:
                cur.val += (l1.val + l2.val)
                l1 = l1.next
                l2 = l2.next
            elif l1:
                cur.val += l1.val
                l1 = l1.next
            elif l2:
                cur.val += l2.val
                l2 = l2.next

            if cur.val > 9:
                carry = cur.val // 10
                cur.val = cur.val % 10


        if carry:
            cur.next = ListNode(carry)

        return res.next
    # 主逻辑
    new_l1 = reverseList(l1)
    new_l2 = reverseList(l2)
    new_l3 = addTwoNumbers(new_l1, new_l2)
    return reverseList(new_l3)

0 赞同 0 条回复

Bello~ 普通 2023年6月24日上午12:25

思路：反转链表进行相加
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode newL1 = reverse(l1);
        ListNode newL2 = reverse(l2);
        ListNode dummy = new ListNode(0);
        ListNode sumCur = dummy;
        int flag = 0;
        int sum = 0;
        while (newL1 != null && newL2 != null) {
            ListNode temp = new ListNode(0);
            sum = newL1.val + newL2.val + flag;
            flag = sum / 10;
            temp.val = sum % 10;
            sumCur.next = temp;
            sumCur = sumCur.next;
            newL1 = newL1.next;
            newL2 = newL2.next;
        }
        while (newL1 != null) {
            sum = newL1.val + flag;
            flag = sum / 10;
            ListNode temp = new ListNode(0);
            temp.val = sum % 10;
            sumCur.next = temp;
            sumCur = sumCur.next;
            newL1 = newL1.next;
        }
        while (newL2 != null) {
            sum = newL2.val + flag;
            flag = sum / 10;
            ListNode temp = new ListNode(0);
            temp.val = sum % 10;
            sumCur.next = temp;
            sumCur = sumCur.next;
            newL2 = newL2.next;
        }
        if (flag != 0) {
            ListNode temp = new ListNode(0);
            temp.val = flag;
            sumCur.next = temp;
        }
        return reverse(dummy.next);
    }

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

0 赞同 0 条回复

CV大神普通 2023年6月23日下午11:51

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //把两个链表放进队列里面
        ListNode current1 = l1;
        ListNode current2 = l2;
        Deque<ListNode> stack1 = new ArrayDeque<>();
        Deque<ListNode> stack2 = new ArrayDeque<>();
        while (current1 != null) {
            stack1.push(current1);
            current1 = current1.next;
        }
        while (current2 != null) {
            stack2.push(current2);
            current2 = current2.next;
        }
        ListNode result = new ListNode(0);
        //进位
        int carry = 0;
        //留意最后一次，两个队列都空了，最后把进位产生的新阶段放进去
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
            int x = stack1.isEmpty()? 0 : stack1.pop().val;
            int y = stack2.isEmpty()? 0 : stack2.pop().val;
            int sum = x + y +carry;
            carry = sum/10;
            ListNode temp = result.next;
            result.next = new ListNode(sum%10);
            result.next.next = temp;
        }

        return result.next;

    }

时间复杂度O（n）,空间复杂度O（n）

0 赞同 0 条回复

拾陆. 普通 2023年6月23日下午8:44

/**
 * 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* reverseList(ListNode* head){
        if(!head) return nullptr;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur){
            ListNode* node = cur->next;
            cur->next = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        ListNode* cur1 = reverseList(l1);
        ListNode* cur2 = reverseList(l2);
        bool carry = false;
        ListNode* dummy = new ListNode(-1);
        ListNode* result = dummy;
        while(cur1 || cur2 || carry){
            int val1 = cur1 ? cur1->val : 0;
            int val2 = cur2 ? cur2->val : 0;
            ListNode* temp = nullptr;
            temp = new ListNode((val1 + val2 + (carry ? 1 : 0)) % 10);
            if((val1 + val2 + (carry ? 1 : 0)) >= 10){
                carry = true;
            }
            else{
                carry = false;
            }  
            result->next = temp;
            result = result->next;
            cur1 = cur1 ? cur1->next : cur1;
            cur2 = cur2 ? cur2->next : cur2;
        }
        return reverseList(dummy->next);
    }
};

可以

0 赞同 0 条回复

彦，，# 普通 2023年6月23日下午6:59

感觉写的太长了,反转的就不贴了，常规思路，但是把个位和进位分开，进位可单独设一个节点，这样更简单高效。

ListNode* addTwoListNode(ListNode* l1, ListNode* l2) {
      if(!l1) return l2;
      if(!l2) return l1;
      if((!l1) && (!l2)) return l1;
      ListNode* cur = new ListNode(-1);
      ListNode* re = cur;
      bool addOver = false;

      ListNode* rl1 = reverse(l1);
      ListNode* rl2 = reverse(l2);
      while(rl1 || rl2)
      {
        ListNode* temp = nullptr;
        if(rl1 && rl2)
        { 
          int addVal = rl1->val + rl2->val; 
          if(addOver)
          {
            addVal += 1;
            addOver =  false;
          }
          addOver = (addVal >= 10) ? true:false;
          if(addOver) addVal -= 10;
          temp = new ListNode(addVal);
        }else if (rl1){
          if(addOver)
          {
            rl1->val += 1;
            addOver =  false;
          }
          temp = new ListNode(rl1->val);
        }else if (rl2){
          if(addOver)
          {
            rl2->val += 1;
            addOver =  false;
          }
          temp = new ListNode(rl2->val);
        }
        re->next = temp;
        re = re->next;
        if(rl1) rl1 = rl1->next;
        if(rl2) rl2 = rl2->next;
      }
      if(addOver)
      {
         ListNode* temp = new ListNode(1);
          re->next = temp;
          re = re->next ;
      }
      return  reverse(cur->next);
    }

0 赞同 0 条回复

Yodl. 普通 2023年6月23日下午1:08

先反转链表，然后从个位数开始相加
时间复杂度:O(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 {
public:
    ListNode addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        auto r1 = reverse(l1), r2 = reverse(l2);
        // add
        bool add10 = false;
        auto curr_r1 = r1, curr_r2 = r2, curr=dummy;
        while(curr_r1 || curr_r2) {
            int res = 0;
            if(curr_r1) {
                res += curr_r1->val;
                curr_r1 = curr_r1->next;
            }
            if(curr_r2) {
                res += curr_r2->val;
                curr_r2 = curr_r2->next;
            }
            res += add10;
            int digit = res % 10;
            add10 = res >= 10 ? true : false;
            curr->next = new ListNode(digit);
            curr = curr->next;
        }
        if(add10) curr->next = new ListNode(1);
        return reverse(dummy->next);
    }

ListNode* reverse(ListNode* head) {
    if(!head || !head->next) return head;
    ListNode *newHead = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

};

0 赞同 1 条回复

彦，，# 普通 @ Yodl. 2023年6月23日下午7:04

很清晰的思路，就是13行是不是得ListNode*？

登录以回复

Tlhey 普通 2023年6月23日上午2:56

“`C++
class Solution {
public:

ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while(cur){
        ListNode* nxt = cur->next;
        cur -> next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;

}

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* l1_r = reverseList(l1);
    ListNode* l2_r = reverseList(l2);
    ListNode* ans_r = new ListNode(0);
    ListNode* ans_head = ans_r;
    int res=0, num=0;
    while(l1_r||l2_r||res){
        num = res + (l1_r !=nullptr ? l1_r->val : 0) + (l2_r !=nullptr ? l2_r->val : 0);
        //printf("%d ", (l1 !=nullptr ? l1_r->val : 0));
        res = num / 10;
        num = num % 10;
        if(l1_r)l1_r = l1_r->next;
        if(l2_r)l2_r = l2_r->next;
        ans_r->val = num;
        ans_r->next = new ListNode(0);
        if(l1_r||l2_r||res)ans_r = ans_r->next;
        //printf("%d %d %d %d \n", num, res, ans_r->val, l1_r->val);
    }
    ans_r->next = (l1_r!=nullptr) ? l1_r : l2_r;
    //printf("%d\n", (l1_r!=nullptr) ? l1_r->val : l2_r->val);
    return reverseList(ans_head);
}//中文

};
“`

0 赞同 0 条回复

残月冷骄阳普通 2023年6月23日上午12:16

思路

先反转链表，然后从个位数开始相加

解题方法

反转链表，从个位数相加，注意进位处理。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$
空间复杂度:

添加空间复杂度, 示例： $O(1)$

Code

“`Java []

/**
* 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 reverL1 = reversalNode(l1);
ListNode reverL2 = reversalNode(l2);
ListNode prv = null;
int add = 0;

//判断条件注意有可能最终的List长度大于Max（l1，l2）的情况
while(reverL1 != null || reverL2 !=null || add!=0){
int num1 = reverL1!=null? reverL1.val: 0;
int num2 = reverL2!=null? reverL2.val: 0;
int sum = num1 + num2 + add;
add = sum/10;
prv= new ListNode(sum%10,prv);
reverL1 = reverL1 != null ? reverL1.next : null;
reverL2 = reverL2 != null ? reverL2.next : null;
}
return prv;
}

//先反转链表

ListNode reversalNode(ListNode head){
    ListNode prv = null;
    while (head!=null){
      ListNode next =   head.next;
      head.next = prv;
      prv = head;
      head = next;
    }
    return prv;
}

}

“`

0 赞同 0 条回复

WhyBeBubble 普通 2023年6月22日下午10:59

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode <em>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</em> addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1);
        auto r1 = reverse(l1), r2 = reverse(l2);
        // add
        bool add10 = false;
        auto curr_r1 = r1, curr_r2 = r2, curr=dummy;
        while(curr_r1 || curr_r2) {
            int res = 0;
            if(curr_r1) {
                res += curr_r1->val;
                curr_r1 = curr_r1->next;
            }
            if(curr_r2) {
                res += curr_r2->val;
                curr_r2 = curr_r2->next;
            }
            res += add10;
            int digit = res % 10;
            add10 = res >= 10 ? true : false;
            curr->next = new ListNode(digit);
            curr = curr->next;
        }
        if(add10) curr->next = new ListNode(1);
        return reverse(dummy->next);
    }

<pre><code>ListNode* reverse(ListNode* head) {
    if(!head || !head->next) return head;
    ListNode *newHead = reverse(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}
</code></pre>

};

0 赞同 0 条回复

跋扈疙瘩汤普通 2023年6月22日下午10:31

只用单链表有点繁琐

/**
 * 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) {}
 * };
 */
// 只使用单链表，不使用其他数据结构（如栈、队列等），难点在于进位
// 逆序
// 链表也可以使用swap
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* l3 = new ListNode(0);
        ListNode* prev = l3;
        while (l1 && l2) {
            l3->next = new ListNode(l1->val + l2->val);
            l1 = l1->next;
            l2 = l2->next;
            l3 = l3->next;
        }

        ListNode* dummy = new ListNode(0);
        if (l1) dummy->next = l1;
        else if(l2) dummy->next = l2;
        //else return prev->next;
        dummy = dummy->next;

        while (dummy) {
            l3->next = new ListNode(dummy->val); 
            l3 = l3->next;
            dummy = dummy->next;
            }

        ListNode* cur3 = prev;
        cur3 = cur3->next;
        ListNode* temp;
        while (cur3) {
            // 考虑进位增加节点的情况
            if (cur3->val > 9 && cur3->next) {                
                cur3->val -= 10;
                cur3->next->val++;
                }
            temp = cur3;
            cur3 = cur3->next;
        }  
        if (temp->val > 9) {
            temp->val -= 10;
            temp->next = new ListNode(1);
        }
        prev = prev->next;
        return prev;                    
        }

};

0 赞同 0 条回复

* 普通 2023年6月22日下午9:46

c实现
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
int sa[1024],topa=0,sb[1024],topb=0,s[1024],top=0;
int dec=0;
for(;l1;l1=l1->next)
{
sa[topa++]=l1->val;
}
for(;l2;l2=l2->next)
{
sb[topb++]=l2->val;
}
for(;topa||topb;top++)
{
if(topa)dec+=sa[–topa];
if(topb)dec+=sb[–topb];
s[top]=dec%10;
dec/=10;
}
if(dec>0||top0)
{
s[top++]=dec;
}
struct ListNode *dy=malloc(sizeof(struct ListNode)), *p;
p=dy;
for(;–top!=-1;)
{
p->next=malloc(sizeof(struct ListNode));
p=p->next;
p->val=s[top];
p->next=NULL;
}
return dy->next;
}

0 赞同 0 条回复

zll 普通 2023年6月22日下午5:59

c实现
反转求和，再反转；
提交了5次，才通过
注意：边界情况
[9,9] [9]
[0] [3,7]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reserve(struct ListNode* head){  //链表反转
    if(!head||!head->next)
        return head;
    struct ListNode *newHead, *cur, *temp;
    cur=head->next;
    newHead=head;
    newHead->next=NULL;
    while(cur){
        temp=cur->next;
        cur->next=newHead;
        newHead=cur;
        cur=temp;
    }
    return newHead;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    if(!l1){
        return l2; 
    }else if (!l2){
        return l1;
    }

    struct ListNode *newl1, *newl2;
    newl1=reserve(l1);  // 反转链表
    newl2=reserve(l2);

    struct ListNode *curl1,*curl2, *pre;
    curl1=newl1;
    curl2=newl2;
    int add=0;   //遍历求和
    while(curl1&&curl2){
        add=curl1->val+curl2->val;
        if(add>=10){ //进位处理
            curl1->val=add-10;
            if(curl1->next){
                curl1->next->val+=1;
            }else{
                struct ListNode *temp =(struct ListNode *) malloc(sizeof(struct ListNode));
                temp->val=1;
                temp->next = NULL;
                curl1->next=temp;
            }
        }else{
            curl1->val=add;
        }
        pre=curl1;  //防止curl1为空退出的情况，此时如果curl2不为空，可能被丢弃
        curl1=curl1->next;
        curl2=curl2->next;
        add=0;
    }
    if(!curl1){
        pre->next=curl2;
    }else if(curl1->val>9){  //curl2为空退出的情况，判断最后curl1是否存在进位情况
        while(curl1){
            if(curl1->val>9){
                curl1->val=curl1->val-10;
                if(curl1->next){
                    curl1->next->val+=1;
                }else{
                    struct ListNode *temp =(struct ListNode *) malloc(sizeof(struct ListNode));
                    temp->val=1;
                    temp->next = NULL;
                    curl1->next=temp;
                }
            }else{
                break;
            }
            curl1=curl1->next;
        }
    }

    return reserve(newl1); 
}

0 赞同 0 条回复

désire. 普通 2023年6月22日上午11:38

C++实现：
class Solution {
public:
ListNode* reverseList(ListNode* head)
{
//反转链表
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* tmp;
while(cur)
{
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
if(l1 nullptr) return l2;
else if(l2 nullptr) return l1;
ListNode* newl1 = reverseList(l1);
ListNode* newl2 = reverseList(l2);
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
int carry = 0;
while(newl1 != NULL || newl2 != NULL)
{
int val1 = newl1 NULL ? 0 : newl1->val;
int val2 = newl2 NULL ? 0 : newl2->val;
int sum = val1 + val2 + carry;
carry = sum / 10;
cur->next = new ListNode(sum % 10);
cur = cur->next;
if(newl1)
newl1 = newl1->next;
if(newl2)
newl2 = newl2->next;
}
//处理最后一个进位
if(carry 1)
{
cur->next = new ListNode(1);
}
return reverseList(dummy->next);
}
};

0 赞同 0 条回复

断舍离永久会员 2023年6月22日上午8:47

class Solution {
    public ListNode addTwoNode(ListNode l1, ListNode l2) {
        //反转2个链表
        ListNode reverseL1 = reverseList(l1);
        ListNode reverseL2 = reverseList(l2);

        //返回的结果头节点，先给一个初始节点
        ListNode newListNode = new ListNode(0);

        //将指向给一个临时节点，用于往后遍历
        ListNode temp = newListNode;
        //进位值
        int carryValue = 0;

        //当两节点都走到null时，结束循环
        while (reverseL1 != null || reverseL2 != null){
            //当前位数的值
            int val;
            if(reverseL1 == null){
                val = reverseL2.val + carryValue;
            }else if(reverseL2 == null){
                val = reverseL1.val + carryValue;
            }else {
                val = reverseL1.val + reverseL2.val + carryValue;
            }
            //算完当前位的结果后，将进位值清0
            carryValue = 0;

            //需要进位的情况
            if(val >= 10){
                //更新进位值
                carryValue = 1;
                //更新对应位数
                temp.next = new ListNode(val - 10);
            }else {
                temp.next = new ListNode(val + carryValue);
            }
            temp = temp.next;

            //确保不会出现空指针异常
            if(reverseL1 != null){
                reverseL1 = reverseL1.next;

            }
            if(reverseL2 != null){
                reverseL2 = reverseL2.next;
            }
        }

        //说明还有一个进位，要再添加一个节点
        if(carryValue == 1){
            temp.next = new ListNode(1);
        }

        //反转更新好的链表
        ListNode reverseNewListNode = reverseList(newListNode.next);
        return reverseNewListNode;
    }

    public ListNode reverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

0 赞同 0 条回复

花老爷普通 2023年6月22日上午8:20

按照思路

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        reverse(l1);
        reverse(l2);
        ListNode l3 = new ListNode(-1);
        ListNode l = l3;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 = l2 == null ? 0 : l2.val;
            int sum = v1 + v2 + carry;
            l.next = new ListNode(sum % 10);
            l = l.next;
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry == 1) {
            l.next = new ListNode(1);
        }
        ListNode res = l3.next;
        l3.next = null;
        return reverse(res);
    }

    private ListNode reverse(ListNode l) {
        if (l == null || l.next == null) {
            return l;
        }
        ListNode pre = l, cur = l.next;
        pre.next = null;
        while (cur.next != null) {
            ListNode post = cur.next;
            cur.next = pre;
            pre = cur;
            cur = post;
        }
        cur.next = pre;
        return cur;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日上午7:56

C++
先翻转两个链表，然后相加，然后再翻转相加后的链表，返回结果
TC: O(n), n为两个链表的长度和
SC: O(1)

// struct ListNode {
//     int val;
//     ListNode* next;
//     ListNode(int _val) : val(_val), next(NULL) {}
// };


ListNode* reverse(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;
    while (curr) {
        ListNode* tmp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = tmp;
    }
    return prev;
}

ListNode* addTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) {
        return l2;
    }
    if (!l2) {
        return l1;
    }
    /*
    l1: 1->2->3->4
    l2:       3->4

<pre><code>翻转后变成
l1: 4->3->2->1
l2: 4->3
*/

// reverse l1
ListNode* head1 = reverse(l1);

// reverse l2
ListNode* head2 = reverse(l2);

// return data
ListNode* resDummy = new ListNode(0);
ListNode* resCurr = resDummy;

// add
ListNode* curr1 = head1;
ListNode* curr2 = head2;
int carry = 0;
while (carry || curr1 || curr2) {
    // add values
    carry += curr1 ? curr1->val : 0;
    carry += curr2 ? curr2->val : 0;
    // move to next one
    if (curr1) curr1 = curr1->next;
    if (curr2) curr2 = curr2->next;

    int currVal = carry % 10;
    resCurr->next = new ListNode(currVal);
    resCurr = resCurr->next;
    carry = carry / 10;
}
// reverse result
return reverse(resDummy->next);
</code></pre>

}

int main() {
    // init 2 example lists
    // l1: 1->2->3->4
    // l2:       3->4
    ListNode* head1 = new ListNode(1);
    ListNode* curr1 = head1;
    curr1->next = new ListNode(2);
    curr1 = curr1->next;
    curr1->next = new ListNode(3);
    curr1 = curr1->next;
    curr1->next = new ListNode(4);
    curr1 = curr1->next;

<pre><code>ListNode* head2 = new ListNode(3);
ListNode* curr2 = head2;
curr2->next = new ListNode(4);
curr2 = curr2->next;

// result && test 
ListNode* addedList = addTwoLists(head1, head2);

ListNode* curr = addedList;
while (curr) {
    cout << curr->val << "->";
    curr = curr->next;
}
cout << "NULL" << endl;
// Output: 1->2->6->8->NULL
</code></pre>

}

0 赞同 0 条回复

大鑫啊普通 2023年6月22日上午1:02

帮忙完善了下面peach同学的代码，感谢打卡分享，理清了这道题的逻辑

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

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
public class sumList {
    public static void main(String[] args) {
    ListNode l1 = new ListNode(1);
    ListNode tmp = new ListNode(2);
    l1.next = tmp;
    tmp.next = new ListNode(3);
    tmp = tmp.next;
    tmp.next = new ListNode(4);
        System.out.println(l1);
    ListNode l2 = new ListNode(3);
    ListNode tmp2 = new ListNode(4);
    l2.next = tmp2;

        System.out.println(l2);
        ListNode listNode = new Solution().addTwoNumbers(l1, l2);
        System.out.println(listNode);

    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //如果不反转，直接相加 1234 和 34(00) 无法做到末尾对齐，加起来是4634 不符合要求
        l1 = reverse(l1); //先把两个链表反转一下 4321 和 43(00) 相加得到 8621 再反转即可
        l2 = reverse(l2);
        ListNode pre = new ListNode(0);
        ListNode cur = pre; //这里设置两个虚拟节点
        int val1, val2, sum;
        int carry = 0; //初始化值为0
        while(l1 != null || l2 != null){
            val1 = l1 == null ? 0 : l1.val; //空就为0，否则为val
            val2 = l2 == null ? 0 : l2.val;
            sum = val1 + val2 + carry; //计算和，注意把carry带上，是上一位的进位
            carry = sum / 10; //更新carry，下一位的进位
            sum = sum % 10; //这一位的数字
            cur.next = new ListNode(sum); //设置下一个节点
            cur = cur.next; //向后走
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        if(carry == 1){ //如果最后一位还有进位，说明位数增多，在后面补上一个高位1即可
            cur.next = new ListNode(1);
        }
        return reverse(pre.next); //不设置pre的话，最后找不到头节点，最后再反转一下即可
    }
    //给出反转链表的方法，传入头节点，返回反转后的头节点
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode p = head;
        ListNode c = head.next;
        ListNode t;
        while(c != null){
            t = c.next;
            c.next = p;
            if(p == head) p.next = null;
            p = c;
            c = t;
        }
        return p;
    }
}

0 赞同 0 条回复

江畅普通 2023年6月21日下午11:30

#include <iostream>
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) { return head; }

        ListNode* prev = nullptr;
        ListNode* cur = head;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

    // 链表相加
    ListNode* addList(ListNode* l1, ListNode* l2) {
        // 先反转两个链表
        l1 = reverseList(l1);
        l2 = reverseList(l2);

        ListNode* dummyHead = new ListNode(0);
        ListNode* prev = dummyHead;
        int k = 0;  // 记录进位

        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        while (cur1 != nullptr && cur2 != nullptr) {

            // 各位和
            int nodeSum = cur1->val + cur2->val + k;

            // result 链表的节点
            ListNode* cur = new ListNode(nodeSum % 10);
            k = nodeSum / 10;

            prev->next = cur;
            prev = cur;

            cur1 = cur1->next;
            cur2 = cur2->next;
        }

        while (cur1 != nullptr) {
            int nodeSum = cur1->val + k;
            ListNode* cur = new ListNode(nodeSum % 10);
            k = nodeSum / 10;
            prev->next = cur;
            prev = cur;
            cur1 = cur1->next;
        }
        while (cur2 != nullptr) {
            int nodeSum = cur2->val + k;
            ListNode* cur = new ListNode(nodeSum % 10);
            k = nodeSum / 10;
            prev->next = cur;
            prev = cur;
            cur2 = cur2->next;
        }

        if (k) {
            ListNode* cur = new ListNode(k);
            prev->next = cur;
        }

        return reverseList(dummyHead->next);
    }
};

int main() {
    Solution s;
    ListNode node1(1);
    ListNode node2(2);
    ListNode node3(3);
    ListNode node4(4);

    ListNode node5(3);
    ListNode node6(4);

    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;

    node5.next = &node6;

    ListNode* res = s.addList(&node1, &node5);

    while (res != nullptr) {
        cout << res->val << endl;
        res = res->next; 
    }
    return 0;
}

0 赞同 0 条回复

行动派小彩笔普通 2023年6月21日下午11:23

本地IDE

没有bug
时间复杂度O(max{m,n}),最大链表长度，空间复杂度(m+n)，除了题目要求的输入链表外，还有一个结果链表，题目链表长度和

思路

先反转，每个对应节点元素相加，算进位，最后在反转输出接表

#include
using namespace std;
struct listnode
{
    int val;
    listnode* next;
    listnode(int x):val(x),next(nullptr){}
};

listnode* reverseList(listnode* head)
{
    listnode* pre = nullptr, *cur = head;
    while (cur)
    {
        listnode* tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre; // 如果head==nullptr,pre返回的依旧是pre，不需要边界判断
}
void printList(listnode* head)
{
    if (head == nullptr) return;
    listnode* cur = head;
    while (cur)
    {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

int main()
{
    int num;
    listnode* head1 = new listnode(-1);
    listnode* cur1 = head1;
    while (cin >> num)
    {
        cur1->next = new listnode(num);
        cur1 = cur1->next;
        if (cin.get() == '\n') break;
    }

    listnode* head2 = new listnode(-1);
    cur1 = head2;
    while (cin >> num)
    {
        cur1->next = new listnode(num);
        cur1 = cur1->next;
        if (cin.get() == '\n') break;
    }
    if (!head1->next || !head2->next)
    {
        cout << "存在空链表！" << endl;
        return 0;
    }
    printList(head1->next);
    printList(head2->next);
    head1->next = reverseList(head1->next);
    head2->next = reverseList(head2->next);
    printList(head1->next);
    printList(head2->next);

    cur1 = head1->next;
    listnode* cur2 = head2->next;

    listnode* ans = new listnode(-1);
    listnode* cur = ans;
    int carry = 0,val1,val2;//表示进位
    while (cur1 || cur2)
    {
        val1 = cur1 == nullptr ? 0 : cur1->val;
        val2 = cur2 == nullptr ? 0 : cur2->val;
        int sum = val1 + val2+carry;
        carry = sum / 10;
        sum %= 10;
        cur->next = new listnode(sum);
        cur = cur->next;
        if(cur1)
            cur1 = cur1->next;
        if(cur2)
            cur2 = cur2->next;
    }
    if (carry == 1) cur->next = new listnode(1);
    ans->next = reverseList(ans->next);
    printList(ans->next);
    return 0;
}

0 赞同 0 条回复

Jerry 普通 2023年6月21日下午11:17

public class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
    public ListNode addTwoListNodes(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0; //代表进位
        while (head1 != null || head2 != null) { //遍历head1 head2
            int sum = carry;
            if (head1 !== null) {
                sum += head1.val;
                head1 = head1.next;
            }
            if (head2 !== null) {
                sum += head2.val;
                head2 = head2.next;
            }

            carry = sum / 10; //计算进位
            curr.next = new ListNode(sum % 10); //生成相加后node的每一个节点
            curr = curr.next;
        }
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        return dummy.next;
    }
}

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

1 赞同 0 条回复

怀瑾永久会员 2023年6月21日下午11:07

C++实现单链表相加

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        while (l1) {
            s1.push(l1 -> val);
            l1 = l1 -> next;
        }
        while (l2) {
            s2.push(l2 -> val);
            l2 = l2 -> next;
        }
        int carry = 0;
        ListNode* ans = nullptr;
        while (!s1.empty() or !s2.empty() or carry != 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();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            auto curnode = new ListNode(cur);
            curnode -> next = ans;
            ans = curnode;
        }
        return ans;
    }
};

0 赞同 0 条回复

jhfuture 普通 2023年6月21日下午10:42

java实现

class Node{
    int val;
    Node next=null;
    Node(int val){
        this.val=val;
    }
}
public class addOperation {

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node1 = new Node(1);
        Node node2= new Node(2);
        node.next=node2;
        Node add = Add(node, node1);
        while(add!=null){
            System.out.println(add.val);
            add=add.next;
        }
    }
public static Node  Add(Node node1,Node node2){
//    1.对两个链表进行原地反转
    Node tmp=node1.next;
    Node pre=null;
    Node cur=node1;
    int leng1=0;
    int leng2=0;
    while (cur!=null){
        cur.next=pre;
        pre=cur;
        cur=tmp;
        tmp=cur==null?null:cur.next;
        leng1++;
    }
    Node tmp2=node2.next;
    Node pre2=null;
    Node cur2=node2;
    while (cur2!=null){
        cur2.next=pre2;
        pre2=cur2;
        cur2=tmp2;
        tmp2=cur2==null?null:cur2.next;
        leng2++;
    }
//   现在 pre 和 pre2为反转后的结点
//    2.相加
    Node pre1Tmp=pre;
    Node pre2Tmp=pre2;
    if (leng1>leng2){
        while(pre2!=null){
            pre.val+= pre2.val;
            pre2=pre2.next;
            pre=pre.next;
        }
        //将结果反转后再返回
        Node preT=null;
        Node curT=pre1Tmp;
        Node tmpT=pre1Tmp.next;
        while (curT!=null){
            curT.next=preT;
            preT=curT;
            curT=tmpT;
            tmpT=curT==null?null:curT.next;
        }
        return preT;
    }else{
        while(pre!=null){
            pre2.val+= pre.val;
            pre2=pre2.next;
            pre=pre.next;
        }

        //将结果反转后再返回
        Node preT=null;
        Node curT=pre2Tmp;
        Node tmpT=pre2Tmp.next;
        while (curT!=null){
            curT.next=preT;
            preT=curT;
            curT=tmpT;
            tmpT=curT==null?null:curT.next;
        }
        return preT;
    }

}
}

思路：原地反转即可。
时间复杂度为n,空间复杂度为1

0 赞同 0 条回复

Vow the vow。普通 2023年6月21日下午10:42

链表反转+同时操作两个链表（加法模拟）

static class Node{
        private int val;
        private Node next;

        Node(int val){
            this.val= val;
            next = null;
        }
    }


    public static void main(String[] args) {
        // 创建链表
        int[] num1 = {1,2,3,4};
        int[] num2 = {3,4};

        Node list1;
        Node list2;

        list1 = buildList(num1);
        list2 = buildList(num2);

        // 1.反转链表
        list1 = reverseList(list1);
        list2 = reverseList(list2);
        // 2.模拟加法
        Node res = addList(list1,list2);
        res = reverseList(res);
        Node cur = res;
        while(cur!= null){
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    private static Node buildList(int[] num){
        Node list = new Node(-1);
        Node node = list;
        for (int i = 0; i < num.length; i++) {
            node.next = new Node(num[i]);
            node = node.next;
        }
        return list.next;
    }

    private static Node reverseList(Node head){
        if(head == null || head.next == null) return head;
        Node newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return  newHead;
    }

    private static Node addList(Node list1, Node list2){
        Node res = new Node(-1);
        int flag = 0;
        int val1,val2,val;
        Node cur = res;
        while(list1 != null || list2 != null){
            if(list1 != null){
                val1 = list1.val;
                list1 = list1.next;
            }else{
                val1 = 0;
            }
            if(list2 != null){
                val2 = list2.val;
                list2 = list2.next;
            }else{
                val2 = 0;
            }
            val = val1 + val2 + flag;
            cur.next = new Node(val%10);
            flag = val / 10;
            cur = cur.next;
        }
        if(flag != 0){
            cur.next = new Node(flag);
        }
        return res.next;
    }

0 赞同 0 条回复

局外人普通 2023年6月21日下午10:39

思路：先逆转两条链表，从末尾（个位）相加，考虑进位，不断增加新节点接入新的头节点。最终再次逆转该新链表。

(此处逆转链表看上文， 以下直接考虑传入逆转后的链表)
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head=new ListNode(-1);

        ListNode *p1=l1, *p2=l2;
        int carry=0, value=0;
        ListNode *cur=head;
        while(p1!=NULL && p2!=NULL){
            int sum=p1->val + p2->val;
            value = (sum + carry)%10;
            carry = (sum + carry)/10;
            cur->next = new ListNode(value);
            cur = cur->next;

            p1=p1->next;
            p2=p2->next;
        }

        while(p1!=NULL){
            int sum=(p1->val + carry);
            value = sum%10;
            carry = sum/10;
            cur->next = new ListNode(value);
            cur = cur->next;

            p1=p1->next;
        }
        while(p2!=NULL){
            int sum=(p2->val + carry);
            value = sum%10;
            carry = sum/10;
            cur->next = new ListNode(value);
            cur = cur->next;

            p2=p2->next;
        }

        if(carry==1){
            cur->next = new ListNode(1);
        }
        return head->next;
    }
};

0 赞同 0 条回复

硬核洋葱普通 2023年6月21日下午10:23

/**
 * 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* ReverseList(ListNode* head){
        ListNode* prev = head;
        ListNode* node = head->next;
        while(node){
            ListNode* temp = node->next;
            if(prev == head)
                prev->next = NULL;
            node->next = prev;
            prev = node;
            node = temp;
        }
        return prev;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* rl1 = ReverseList(l1);
        ListNode* rl2 = ReverseList(l2);

        ListNode* node1 = rl1, *node2 = rl2;
        ListNode* dummyhead = new ListNode(0);
        int carrybit = 0;
        while(node1 && node2){
            int val = node1->val + node2->val + carrybit;
            if(val >= 10){
                val -= 10;
                carrybit = 1;
            }
            else
                carrybit = 0;

            ListNode* ansnode = new ListNode(val);
            ansnode->next = dummyhead->next;
            dummyhead->next = ansnode;

            node1 = node1->next;
            node2 = node2->next;
        }

        if(!node1)
            node1 = node2;
        while(node1){
            int val = node1->val+ carrybit;
            if(carrybit){
                if(val >= 10)
                    val -= 10;
                else
                    carrybit = 0;
            }

            ListNode* ansnode = new ListNode(val);
            ansnode->next = dummyhead->next;
            dummyhead->next = ansnode;

            node1 = node1->next;
        }

        if(carrybit){
            ListNode* ansnode = new ListNode(1);
            ansnode->next = dummyhead->next;
            dummyhead->next = ansnode;
        }

        return dummyhead->next;
    }
};

时间复杂度O(m+n)，空间复杂度因为开了一条新链存储结果，应该是O(max(m, n))吧
我在leetcode上见过这道题《链表中的两数相加》
先写一个反转链表函数，然后创建一个新链表，使用头插法保存每位的结果。最后如果还有进位，需要在前面再头插一个1

0 赞同 0 条回复

伏月三十普通 2023年6月21日下午9:32

在本地测了几个是对的，写了很久。。。
public class AddList {
public static void main(String[] args) {
ListNode a=new ListNode(7);
a.next=new ListNode(3);
ListNode b=new ListNode(0);
ListNode node = addList(a, b);
System.out.println(node.val);
System.out.println(node.next.val);
//System.out.println(node.next.next.val);
}

public static ListNode addList(ListNode a, ListNode b){
    ListNode reverseA = reverse(a);
    ListNode reverseB = reverse(b);
    ListNode p1=reverseA;
    ListNode p2=reverseB;

    ListNode s=new ListNode(-1);  //到时候返回s.next
    ListNode p3=s;
    //把反转后的链表每一位都加起来 只要有一个为空就退出循环  把剩下的链表加到新的链表上(类似于合并链表)
    while (p1!=null && p2!=null){
        p3.next=new ListNode(p1.val+ p2.val);
        p3=p3.next;
        p1=p1.next;
        p2=p2.next;
    }
    if(p1!=null){
        p3.next=p1;
    }
    if(p2!=null){
        p3.next=p2;
    }

    //现在得到了未反转 需要处理进位的链表
    p3=s.next;
    while (p3!=null){
        if(p3.val>=10){
            //先处理链表的头节点 从当前节点处理
            //把当前位置的值要先保存下来
            int temp=p3.val; //比如temp=19
            p3.val=temp%10;
            if(p3.next==null){
                p3.next=new ListNode(temp/10);
                break;
            }else {
                p3.next.val=(temp/10)+ p3.next.val;
            }
        }
        p3=p3.next;
    }
    return reverse(s.next);

}

private static ListNode reverse(ListNode head){
    if(head==null || head.next==null){
        return head;
    }
    ListNode last=reverse(head.next);
    head.next.next=head;
    head.next=null;
    return last;
}

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

}
}

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月21日下午9:19

思路：先各自反转，逐个节点相加，注意进位，将结果反转
时间复杂度：O(n)
额外空间复杂度：O(1)

public static ListNode sumList(ListNode t1, ListNode t2){
        ListNode t1reverse = reverse(t1);
        ListNode t2reverse = reverse(t2);

    int cin = 0;
    ListNode newList = new ListNode(-1);
    ListNode newListtmp = newList;
    while(t1reverse != null || t2reverse != null){
        int res1 = t1reverse == null ? 0 : t1reverse.val;
        int res2 = t2reverse == null ? 0 : t2reverse.val;

        int res = res1 + res2 + cin;
        cin = res / 10;
        res = res % 10;
        newListtmp.next = new ListNode(res);

        newListtmp = newListtmp.next;
        if(t1reverse != null) {
            t1reverse = t1reverse.next;
        }
        if(t2reverse != null){
            t2reverse = t2reverse.next;
        }
    }

    if(cin > 0){
        newListtmp.next = new ListNode(cin);
    }

    return reverse(newList.next);
}

public static ListNode reverse(ListNode head){
    ListNode prev = null;
    ListNode after = null;
    while(head != null){after = head.next;
       head.next = prev;
       prev = head;
       head = after;
    }
    return prev;
}

0 赞同 0 条回复

张开怀普通 2023年6月21日下午7:28

链表反转之后，按位求和，同时需要设置一个进位标志，计算完成后，再进行反转得到结果

class Solution{
public:
     // 反转链表
     ListNode* reverseList(ListNode* head){
          if(head == nullptr || head->next == nullptr){
               return head;
          }
          // 反转子链表
          ListNode* temp = reverseList(head->next);
          head->next->next = head;
          head->next = nullptr;

          return temp;
     }
     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
          l1 = reverseList(l1);
          l2 = reverseLisr(l2);
          // 前置结点，使用辅助结点
          ListNode* pre = new ListNode(0);
          ListNode* cur = pre;
          // carry表进位
         int carry=0;
         while(l1 != nullptr || l2 != nullptr){
              // 补全操作
              int x = l1 == nullptr ? 0 : l1->val;
              int y = l2 == nu;;ptr ? 0 : l2->val;
              int sum = x+y+carry;

              // 求出进位数和本位的sum
              carry = sum / 10;
              sum = sum % 10;

              // 移动结点
              cur->next = new ListNode(sum);
              cur = cur->next;

              if(l1 != nullptr){
                   l1 = l1->next;
              }
              if(l2 != nullptr){
                   l2 = l2->next;
              }
         }
         // 循环结束需要判断是否还需要进位，即是否还需要一个结点
         if(carry == 1){
              cur->next = new ListNode(carry);
         }
         // pre的下一个节点才是真正应该输出的链表头
         return reverseList(pre->next);
     }
}

1 赞同 0 条回复

peach 普通 2023年6月21日下午6:15

思路

这道题有一定难度，关键是补位的问题，比如1234 + 34 = 1268，但我们链表只能从头开始遍历，没法前面补位0
因此我们先把两个链表反转，计算4321 + 4300 = 8621，然后再反转即可
计算每个位置的和的时候，要考虑进位的情况

代码

详细代码，欢迎大家一起讨论~

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //如果不反转，直接相加 1234 和 34(00) 无法做到末尾对齐，加起来是4634 不符合要求
        l1 = reverse(l1); //先把两个链表反转一下 4321 和 43(00) 相加得到 8621 再反转即可
        l2 = reverse(l2);
        ListNode pre = new ListNode();
        ListNode cur = pre; //这里设置两个虚拟节点
        int val1, val2, sum;
        int carry = 0; //初始化值为0
        while(l1 != null || l2 != null){
            val1 = l1 == null ? 0 : l1.val; //空就为0，否则为val
            val2 = l2 == null ? 0 : l2.val;
            sum = val1 + val2 + carry; //计算和，注意把carry带上，是上一位的进位
            carry = sum / 10; //更新carry，下一位的进位
            sum = sum % 10; //这一位的数字
            cur.next = new ListNode(sum); //设置下一个节点
            cur = cur.next; //向后走
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        if(carry == 1){ //如果最后一位还有进位，说明位数增多，在后面补上一个高位1即可
            cur.next = new ListNode(1);
        }
        return reverse(pre.next); //不设置pre的话，最后找不到头节点，最后再反转一下即可
    }
    //给出反转链表的方法，传入头节点，返回反转后的头节点
    private ListNode reverse(ListNode head){ 
        if(head == null || head.next == null) return head;
        ListNode p = head;
        ListNode c = head.next;
        ListNode t;
        while(c != null){
            t = c.next;
            c.next = p;
            if(p == head) p.next = null;
            p = c;
            c = t;
        }
        return p;
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月21日下午5:54

“`cpp
// 用了反转链表
// 特别注意最后一位为10 的情况
// 如果用栈的话，更好处理一点，但是需要的二外空间大
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* newl1 = reverlist(l1);
ListNode* newl2 = reverlist(l2);
ListNode* ans = new ListNode(0);
ListNode* dummy = ans;
int j=0,d=0;
while(newl1 && newl2){
int sum = newl1->val + newl2->val+j;
d = sum%10;
ans->next = new ListNode(d);
j = sum/10;
ans = ans->next;
newl1 = newl1->next;
newl2 = newl2->next;
}
while(newl1){
newl1->val += j;
d = newl1->val %10;
ans->next = new ListNode(d);
j = newl1->val / 10;
ans = ans->next;
newl1 = newl1->next;
}
while(newl2){
newl2->val += j;
d = newl2->val %10;
ans->next = new ListNode(d);
j = newl2->val / 10;
ans = ans->next;
newl2 = newl2->next;
}
ans = reverlist(dummy->next);
if(j!=0){
ListNode* temp = new ListNode(j);
temp->next = ans;
ans = temp;
}
return ans;
}
ListNode* reverlist(ListNode* head){
if(!head || !head->next){
return head;
}
ListNode* newhead = reverlist(head->next);
head->next->next = head;
head->next = nullptr;
return newhead;
}
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月21日下午5:40

//进位这里感觉比较细
//需要考虑得多一些
//想着节省空间，就打算把结果直接放在长链上
//如果开一条新的链应该会好写些
public class 剑指offer {
    public static void main(String[] args) {
        Node list1 = new Node(1);
        list1.next = new Node(2);
        list1.next.next = new Node(3);
        list1.next.next.next = new Node(4);
        Util.printList(list1);

        Node list2 = new Node(9);
        list2.next = new Node(9);
        list2.next.next = new Node(9);
        list2.next.next.next = new Node(9);
        Util.printList(list2);

        Util.printList(addNodeList(list1,list2));

    }
    public static Node addNodeList(Node head1,Node head2){

        //先反转
        head1 = reverseList(head1);
        head2 = reverseList(head2);

        //分别计算长度
        int len1 = getLen(head1);
        int len2 = getLen(head2);

        //长的用来当“目标链”，也就是计算完之后在长链表上更新
        Node longList = len1>len2?head1:head2;
        Node shortList = len1>len2?head2:head1;

        //进位标志
        boolean jinweiFlag = false;

        while(shortList != null){
            int jinwei = jinweiFlag == true?1:0;

            //带进位的求和
            int sum = shortList.value + longList.value + jinwei;
            //更新当前值
            longList.value = sum % 10;

            //判断是否有进位，为下一次求和做准备
            jinweiFlag = sum / 10 == 1?true:false;

            //指针后移，准备计算下一位
            shortList = shortList.next;
            longList = longList.next;
        }

        //此时，如果不需要进位，就直接结束了
        //如果需要进位，还需继续求和

        //还需要进位，且长链表不空
        while(jinweiFlag && longList != null){

            //更新当前值
            longList.value = longList.value + 1 % 10;

            //判断是否有进位，为下一次求和做准备
            jinweiFlag = longList.value + 1 >= 10?true:false;
            //处理下一位
            longList = longList.next;
        }

        //需要进位，链表为空，在末尾加个1就好。
        //但此时longList已经为空，不好拿到尾结点
        //所以先反转，再再头部插入1。
        Node result = reverseList(len1>len2?head1:head2);//计算结果存在长链中，将其反转

        //需要进位，链表为空，在头部加个1
        if(jinweiFlag){
            Node newHead = new Node(1);
            newHead.next = result;
            return newHead;
        }
        return result;
    }
    public static Node reverseList(Node head){
        if(head == null || head.next == null){
            return head;
        }
        Node newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return  newHead;
    }
    public static int getLen(Node head){
        Node cur = head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }
}

0 赞同 0 条回复

Ming 普通 2023年6月21日下午3:06

反转之后考虑两个链表长度相同，进位+1时会空

public class SumLink {
    public static void main(String[] args) {
        Node l1 = new Node(3);
        l1.next = new Node(4);


        Node l2 = new Node(6);
        l2.next = new Node(8);
        l2.next.next = new Node(8);

        Node sum = getSum(l1, l2);
        while (sum != null) {
            System.out.print(sum.val);
            sum = sum.next;
        }
    }
    public static Node getSum(Node l1, Node l2) {
        l1 = reverse(l1);
        System.out.println();
        l2 = reverse(l2);
        Node list1 = l1;
        Node list2 = l2;
        Node dummy = new Node(0,null);
        Node cur = dummy;
        int i = 0;
        List<Integer> list = new ArrayList<>();
        list.add(0);
        while (list1 != null && list2 != null) {
            int n = list1.val + list2.val + list.get(i);
            list1 = list1.next;
            list2 = list2.next;
            int yu = n % 10; //余数
            if (n > 9) {
                list.add(1);
            } else {
                list.add(0);
            }
            cur.next = new Node(yu, null);
            cur = cur.next;
            i++;
        }
        if (list.get(list.size()-1) == 1) {
            if (list1 != null) list1.val += 1;
            else if (list2 != null) list2.val += 1;
        }
        cur.next = list1 == null ? list2 : list1;
        if (list1 == null && list2 == null) {
            cur.next = new Node(1,null);
        }
        return reverse(dummy.next);
    }
    public static Node reverse(Node head) {
        if (head == null) return null;
        Node pre = null;
        while(head != null) {
            Node next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

class Node{
    int val;
    Node next;

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

    public Node(int val) {
        this.val = val;
    }
}

0 赞同 0 条回复

yxy 普通 2023年6月21日下午1:01

参考代码：

class Solution {
public:
    ListNode* reverse(ListNode* head)
    {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* next;
        while(cur)
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur=next;
        }
        return prev;
    }
    ListNode* addSingleLists(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);

        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* dummy = new ListNode;
        ListNode* prev = dummy;
        int k = 0;
        while(cur1&&cur2)
        {
            int sum = cur1->val + cur2->val + k;
            ListNode* cur = new ListNode(sum%10);
            k = sum/10;
            prev->next = cur;
            prev = cur;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        while(cur1)
        {
            int sum = cur1->val + k;
            ListNode* cur = new ListNode(sum%10);
            k = sum/10;
            prev->next = cur;
            prev = cur;
            cur1 = cur1->next;
        }
        while(cur2)
        {
            int sum = cur2->val + k;
            ListNode* cur = new ListNode(sum%10);
            k = sum/10;
            prev->next = cur;
            prev = cur;
            cur2 = cur2->next;
        }
        if(k)
        {
            ListNode* cur = new ListNode(k);
            prev->next = cur;
        }
        return reverse(dummy->next);
    }
};

0 赞同 0 条回复

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

代码参考

共以下 57 个回答

思路

解题方法

复杂度

Code

本地IDE

思路

思路

代码

# 回答此问题取消回复

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

代码参考

共以下 57 个回答

思路

解题方法

复杂度

Code

本地IDE

思路

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复