糖香香普通 2023年6月26日下午7:43

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        List<Integer> list1 = new LinkedList<>();
        List<Integer> list2 = new LinkedList<>();
        while (cur1 != null) {
            list1.add(cur1.val);
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            list2.add(cur2.val);
            cur2 = cur2.next;
        }
        //转成数组
        int[] ints1 = list1.stream().filter(i -> i != null).mapToInt(i -> i).toArray();
        int[] ints2 = list2.stream().filter(i -> i != null).mapToInt(i -> i).toArray();
        ArrayList<Integer> list = new ArrayList<>();
        int a = ints1.length, b = ints2.length;
        int flag = 0;
        while (a > 0 && b > 0) {
            int temp = ints1[a - 1] + ints2[b - 1];
            if (flag == 1) {
                temp += 1;
                flag = 0;
            }
            if (temp >= 10) {
                flag = 1;
            }
            list.add(temp % 10);
            a--;
            b--;
        }
        int[] c = a > b ? ints1 : ints2;
        int e = a > b ? a : b;
        while (e > 0) {
            int temp = c[e - 1];
            if (flag == 1) {
                temp += 1;
                flag = 0;
            }
            if (temp >= 10) {
                flag = 1;
            }
            list.add(temp % 10);
            e--;
        }

        if (list.size() >= 1 && flag == 1) {
            list.add(1);
        }
        ListNode result = new ListNode(-1);
        ListNode temp = result;
        for (int i = list.size() - 1; i >= 0; i--) {
            ListNode res = new ListNode(list.get(i));
            temp.next = res;
            temp = temp.next;
        }
        return result.next;
    }

0 赞同 0 条回复

lucca 普通 2022年12月31日上午2:25

时间复杂度O(N)

空间复杂度O(N)

/**
 * 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) {
        l1 = rev(l1);
        l2 = rev(l2);

        ListNode res = new ListNode();
        ListNode cur = res;
        int last = 0;
        while (l1 != null && l2 != null) {
            int val = l1.val + l2.val + last;
            last = val / 10;
            ListNode node = new ListNode(val % 10);
            cur.next = node;
            cur = node;
            l1 = l1.next;
            l2 = l2.next;
        }

        while (l1 != null) {
            int val = l1.val + last;
            last = val / 10;
            ListNode node = new ListNode(val % 10);
            cur.next = node;
            cur = node;
            l1 = l1.next;
        }

        while (l2 != null) {
            int val = l2.val + last;
            last = val / 10;
            ListNode node = new ListNode(val % 10);
            cur.next = node;
            cur = node;
            l2 = l2.next;
        }

        if (last != 0) cur.next = new ListNode(last);
        return rev(res.next);
    }

    private ListNode rev(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newH = rev(head.next);
        head.next.next = head;
        head.next = null;
        return newH;
    }
}

0 赞同 0 条回复

糖鑫普通 2022年12月4日下午3:10

public class test{
    public static void main(String[] args){
        test t=new test();
        int l1[]= {1,2,3,4};
        int l2[]= {3,4};
        ListNode list1=new ListNode();
        ListNode list2=new ListNode();
        ListNode prev=list1;
        for(int i=0;i<l1.length;i++) {
            ListNode node=new ListNode(l1[i]);
            prev.next=node;
            prev=node;
        }
        prev.next=null;
        prev=list2;
        for(int i=0;i<l2.length;i++) {
            ListNode node=new ListNode(l2[i]);
            prev.next=node;
            prev=node;
        }
        prev.next=null;
        ListNode head=t.linkedListAdd(list1.next,list2.next);
        while(head!=null) {
            System.out.print(head.val);
            head=head.next;
        }
    }

    //反转链表再相加
    public ListNode linkedListAdd(ListNode head1, ListNode head2){
        ListNode head=new ListNode();
        ListNode cur=head;
        int carry=0;//不要用boolean，用int可以直接加进去省判断
        ListNode l1=ReverseList(head1);
        ListNode l2=ReverseList(head2);
        while(l1!=null || l2!=null || carry>0) {
            cur.next=new ListNode();
            cur=cur.next;
            cur.val=carry;
            if(l1!=null) {
                cur.val+=l1.val;
                l1=l1.next;
            }
            if(l2!=null) {
                cur.val+=l2.val;
                l2=l2.next;
            }
            carry=cur.val/10;
            cur.val=cur.val%10;
        }
        return ReverseList(head.next);
    }

    public ListNode ReverseList(ListNode head) {
        ListNode prev=null;
        ListNode cur=head;
        ListNode tmp;
        while(cur!=null) {
            tmp=cur.next;
            cur.next=prev;
            prev=cur;
            cur=tmp;
        }
        return prev;
    }

}

0 赞同 0 条回复

PatNick 普通 2022年11月19日下午5:07

# 反转链表
def reverseList(head):
    if not head or not head.next:
        return head
    before = None
    cur = head
    after = head.next

    while after:
        cur.next = before
        before = cur
        cur = after
        after = after.next

    return cur



def singleNodeAdd(head1,head2):
    # 虚拟头节点
    add_re = Node(0)
    head = add_re
    # 存放进位
    sum = 0
    cur1 = head1
    cur2 = head2
    while cur1 or cur2 or (sum != 0):
        if cur1:
            sum += cur1.val
            cur1 = cur1.next

        if cur2:
            sum += cur2.val
            cur2 = cur2.next



        # 相加后如果大于9，需要进位，当前位置只留下个位数，向后进位1
        head.next =Node(sum%10)
        head = head.next
        # 向下一位进位
        sum = sum / 10
    return add_re.next

0 赞同 0 条回复

如梦似歌普通 2022年11月7日下午8:13

 public ListNode linkedListAdd(ListNode head1, ListNode head2){
        head1 = reverseList(head1);
        head2 = reverseList(head2);

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode p1 = head1;
        ListNode p2 = head2;
        //sum用来存放进位
        int sum = 0;
        while(p1 != null || p2 != null || sum != 0){
            if(p1 != null){
                sum += p1.val;
                p1 = p1.next;
            }
            if(p2 != null){
                sum += p2.val;
                p2 = p2.next;
            }
            cur.next = new ListNode(sum % 10);
            sum = sum / 10;
            cur = cur.next;
        }
        return reverseList(dummy.next);
    }

    /**
     * 链表反转函数
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        //TODO:使用三指针法
        ListNode p = head;
        ListNode cur = head.next;
        ListNode temp;
        while (cur != null){
            temp = cur.next;
            cur.next = p;
            p = cur;
            cur = temp;
        }
        //当cur指针为null时，说明p恰好指向原链表最后一个节点处
        head.next = null;
        head = p;
        return head;
    }

0 赞同 0 条回复

一只骆驼普通 2022年11月3日下午3:40

用哑节点去定位，翻转进位再翻转

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        l1 = reserve(l1);
        l2 = reserve(l2);
        // sum 用来存放进位
        int sum = 0;
        while (l1 != null || l2 != null || sum!=0) {
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(sum % 10);
            sum = sum / 10;
            cur = cur.next;
        }
        return reserve(dummy.next);
    }
    public ListNode reserve(ListNode node){
        ListNode pre = null;
        ListNode cur = node;
        ListNode temp;
        while(cur!=null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

0 赞同 0 条回复

和普通 2022年10月31日下午11:02

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1=reverseList(l1);
        l2=reverseList(l2);
        ListNode list1=l1,list2=l2;
        //创建一个头结点
        ListNode head=new ListNode(-1);
        ListNode list=head;
        //定义数值
        int newVal=0;
        int num=0;
        int carry=0;//进位
        int l1Val=0;
        int l2Val=0;
        while (list1!=null||list2!=null){
            l1Val=list1!=null?list1.val:0;
            l2Val=list2!=null?list2.val:0;
            num=l1Val+l2Val+carry;
            carry=num/10;
            newVal=num%10;
            list.next=new ListNode(newVal);
            list=list.next;
            list1=list1==null?list1:list1.next;
            list2=list2==null?list2:list2.next;
        }
        if (carry>0){
            list.next=new ListNode(carry);
        }
        head = reverseList(head.next);
        return head;
    }
    public ListNode reverseList(ListNode head){
        if (head==null||head.next==null){
            return head;
        }
        ListNode pre=null;
        ListNode list=head;
        ListNode next=list;
        while(list!=null){
            next=list.next;//用来记录下一个节点，防止死循环，因为下面的list.next=pre,会死循环。
            list.next=pre;
            pre=list;
            list=next;
        }
        return pre;
    }

0 赞同 0 条回复

泡芙永久会员 2022年10月31日上午8:59

思路：就是24.反转链表和2.两数相加的综合题
Time：O(n + m)
Space：O(1)

/**
 * 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 {
    // 1.反转链表
    public ListNode  reverseList(ListNode head){
        ListNode cur = head;
        ListNode pre = null;

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

    // 2.两数相加
    public ListNode linkedListAdd(ListNode head1, ListNode head2){
        // 在两条链表上的指针
        ListNode p1 = head1, p2 = head2;
        // 虚拟头节点
        ListNode dummy = new ListNode(-1);
        // 指针 p 负责构建新链表
        ListNode p = dummy;
        // 记录进位
        int carry = 0;
        // 开始执行加法，两条链表走完且没有进位时才能结束循环
        while(p1 != null || p2 != null || carry > 0) {
            // 先加上上次的进位
            int val = carry;
            if(p1 != null) {
                val += p1.val;
                p1 = p1.next;
            }
            if(p2 != null) {
                val += p2.val;
                p2 = p2.next;
            }
            // 处理进位
            carry = val / 10;
            val = val % 10;
            // 构建新节点
            p.next = new ListNode(val);
            p = p.next;
        }
        return dummy.next;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年10月30日上午9:04

package com.mos.yygh.structData;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedHashMap;

/**
 * @author 
 * @version 2022.1.3
 * @date 2022/10/25 8:57
 */
public class ListNode {
    private int val;
    private ListNode next;
    public ListNode(){ }
    public ListNode(int val){
        this.val = val;
    }
    public ListNode(int val,ListNode next){
        this.val = val;
        this.next = next;
    }

    //单链表的相加双栈
    public static ListNode linkedListNode(ListNode head1,ListNode head2) {
        Deque s1 = new ArrayDeque<>();
        Deque s2 = new ArrayDeque<>();
        while (head1 != null) {
            s1.push(head1.val);
            head1 = head1.next;
        }
        while (head2 != null) {
            s2.push(head2.val);
            head2 = head2.next;
        }
        int cur = 0;
        ListNode listNode = null;
        //计算当前的值，并进位
        while (!s1.isEmpty() || !s2.isEmpty() || cur != 0) {
            int a = s1.isEmpty() ? 0 : s1.pop();
            int b = s2.isEmpty() ? 0 : s2.pop();
            int temp = a + b + cur;
            cur = temp / 10;
            temp %= 10;
            ListNode curNode = new ListNode(temp);
            curNode.next = listNode;
            listNode = curNode;
        }
        return listNode;
    }
    public static void show(){
        LinkedHashMaphashMap = new LinkedHashMap<>();

    }

}

0 赞同 0 条回复

王艺超普通 2022年10月29日下午1:33

该问题主要需要翻转连接进行计算

class Solution {
public:
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    ListNode* reverseList(ListNode *pHead)
    {
        if(pHead == nullptr) return pHead;

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

    ListNode* addInList(ListNode* head1, ListNode* head2) {
        if(head1 == nullptr) return head2;
        if(head2 == nullptr) return head1;

        ListNode* reHead1 = reverseList(head1);
        ListNode* reHead2 = reverseList(head2);

        ListNode* res = new ListNode(-1);
        ListNode* head = res;

        int arr = 0;
        while(reHead1 != nullptr || reHead2 != nullptr || arr != 0)
        {
            int val1 = reHead1 == nullptr ? 0 : reHead1->val;
            int val2 = reHead2 == nullptr ? 0 : reHead2->val;

            int temp = val1 + val2 + arr;

            arr = temp/10;
            temp %= 10;

            head->next = new ListNode(temp);
            head = head->next;

            if(reHead1 != nullptr)
                reHead1 = reHead1->next;
            if(reHead2 != nullptr)
                reHead2 = reHead2->next;

        }

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

0 赞同 0 条回复

cute. 普通 2022年10月27日下午5:02

var addTwoNumbers = function(l1, l2) {
    // 这道题需要解决进位问题
    // 空链表
    let dummy = new ListNode();
    // 进位值
    let carry = 0;
    let curr = dummy;
    // 循环遍历
    while(l1 !== null || l2 !== null) {
        let sum = 0;
        if(l1 !== null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if(l2 !== null) {
            sum += l2.val;
            l2 = l2.next;
        }
        sum += carry;
        curr.next = new ListNode(sum%10);
        carry = Math.floor(sum/10);
        curr = curr.next;
    }
    if(carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummy.next;
};

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

0 赞同 0 条回复

lobort 普通 2022年10月26日下午11:18

class SoluTionAdd{
    public ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (head != null){
            cur.next = pre;
            pre = cur;
            cur = head.next;
        }
        return pre;
    }

    public ListNode addTwoListNode (ListNode head1,ListNode head2){
        ListNode listNode = new ListNode(0);
        ListNode p = listNode;
        int sum = 0;
        while (head1 !=null || head2 != null){
            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 ? 1:0;
            p = p.next;
        }
        return listNode.next;
    }
}

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

有思路但是没写出来

0 赞同 0 条回复

xye 普通 2022年10月26日下午9:03

func linkedListAdd(l1 *ListNode, l2 *ListNode) *ListNode {
    a := addTwoNumbers(reverseList(l1), reverseList(l2))
    return reverseList(a)
}

// 反转链表
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    node := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return node
}

// 单链表相加，参考leetcode 面试题02.05
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    n1, n2 := l1, l2
    var tmp *ListNode
    for ; n1 != nil && n2 != nil; n1, n2 = n1.Next, n2.Next {
        n1.Val = n1.Val + n2.Val
        if n1.Next == nil {
            tmp = n1
        }
    }
    if n1 == nil {
        tmp.Next = n2
    }
    node1 := l1
    for node1 != nil {
        if node1.Val > 9 {
            node1.Val %= 10
            if node1.Next != nil {
                node1.Next.Val = node1.Next.Val + 1
            } else {
                node1.Next = &ListNode{Val: 1}
            }
        }
        node1 = node1.Next
    }
    return l1
}

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

0 赞同 0 条回复

symbol 普通 2022年10月26日下午7:50

func addTwoNumbers(head1 *ListNode, head2 *ListNode) *ListNode {
    head1 = d_ReverseChain(head1) // 链表翻转
    head2 = d_ReverseChain(head2)
    cur1,cur2 := head1,head2
    l3 := &ListNode{} //建立一个新链表
    cur := l3
    carry := 0 // 先前进一位的具体值
    for cur1 != nil || cur2 != nil {
        sum := 0
        if cur1 != nil {
            sum +=cur1.Val
            cur1 = cur1.Next
        }
        if cur2 != nil {
            sum += cur2.Val
            cur2 = cur2.Next
        }
        remain := (sum + carry) % 10 // 求余 例如12 % 计算 结果为 2 
        carry = (sum + carry) / 10 //取整数 如12 / 计算 结果为 1 
        cur.Next = &ListNode{  //建立节点
            Val:remain,
        }
        cur = cur.Next
    }
    if carry != 0 {
        cur.Next = &ListNode{
            Val:carry,
        }
    }
    return d_ReverseChain(l3.Next)
}

func d_ReverseChain(list *ListNode) *ListNode{ //递归法
    if list == nil || list.Next == nil {
        return list
    }
    newhead := d_ReverseChain(list.Next)
    list.Next.Next = list
    list.Next = nil
    return newhead
}
func ReverseChain(list *ListNode) *ListNode{ //原地法
    if list == nil {
        return nil
    }
    var pre *ListNode
    cur := list
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

0 赞同 0 条回复

虾仁猪心普通 2022年10月26日下午7:43

思路：单链表相加，两个链表的长短不一，但是我们将两个链表分别翻转后，个位就是从头节点开始的节点了，
这里需要注意，要声明一个变量记录进位。然后每次两个链表相加时都要再加上进位的数字。
最后移动指针的时候要先判断这两个链表目前所在的结点是否为空，若为空则不能移动指针（这样就能避免空指针异常了）。

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;
        }
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        int count = 0;
        while(head1!=null || head2!=null || count != 0){
            int val1 = head1 == null? 0 : head1.val;
            int val2 = head2 == null? 0 : head2.val;
            int temp = val1+val2+count;
            count = temp/10;
            temp = temp%10;
            cur.next = new ListNode(temp);
            cur = cur.next;
            if(head1 != null){
                head1 = head1.next;
            }
            if(head2 != null){
                head2 = head2.next;
            }

        }
        return reverse(res.next);

    }
    public static ListNode reverse (ListNode l1) {
        if (l1 == null) {
            return l1;
        }
        ListNode pre = null;
        ListNode cur = l1;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        return pre;
    }
}

0 赞同 0 条回复

Haoyun 普通 2022年10月26日下午6:08

//  反转链表
 const reverseList = function(head) {
    let pre=null;
    let cur=head;
   while(cur){
      let temp=cur.next;
      cur.next=pre;
      pre=cur;
      cur=temp;
   }
   return pre;
}
var addTwoNumbers = function(l1, l2) {
    let newL1 = reverseList(l1);
    let newL2 = reverseList(l2);
    // 处理进位
    let carry = 0;
    let dummy = new ListNode(-1);
    let cur = dummy;
    while(newL1 || newL2 || carry) {
        let sum = 0;
        if(newL1) {
          sum+= newL1.val;
          newL1 = newL1.next;
        }
        if(newL2) {
            sum+= newL2.val;
            newL2 = newL2.next;
        }
        if(carry) {
            sum++;
            carry = 0;
        }
        carry = sum > 9 ? 1 : 0;
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
    }
    return reverseList(dummy.next);
}

0 赞同 0 条回复

cxxz 普通 2022年10月26日下午3:02

根据帅老师的提示，先原地反转直接解决了原本的向前进位的问题，此时只需next节点进位即可。采用了ret的链表直接上长度比较长的，在其基础之上相加另一条链表。最后再翻转返回。

ListNode* reverse(ListNode* head, int* head_len) {
        ListNode *pre=nullptr, *cur, *temp;
        cur = head;
        while (cur != nullptr){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
            *head_len ++;
        }
        return pre;
    }

    ListNode* linkedListAdd(ListNode* head1, ListNode* head2) {
        // 反转
        ListNode *newHead1, *newHead2;
        int head1_len = 0, head2_len = 0;

        newHead1 = reverse(head1, &head1_len);
        newHead2 = reverse(head2, &head2_len);

        ListNode* ret = head1_len >= head2_len ? newHead1:newHead2;
        ListNode* ret_head = ret;
        int jinwei = 0;
        while ( newHead1 != nullptr && newHead2 != nullptr ) {
            if ( jinwei == 1 ) {
                ret->val ++;
                jinwei = 0;
            }
            int temp_res = newHead1->val + newHead2->val;
            if ( temp_res > 9 ) {
                jinwei = 1;
                ret->val = temp_res - 10;
            } else {
                ret->val = temp_res;
            }
            newHead1 = newHead1->next;
            newHead2 = newHead2->next;
            ret = ret->next;
        }
        if ( jinwei == 1 ) {
            ret->val ++;
        }
        return reverse(ret_head, &head1_len);
    }

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

0 赞同 0 条回复

潜行1 我是火车王！普通 2022年10月26日下午1:01

思路对了，代码水平不够
复现的参考代码
时间 N 空间 1

func reverseList(head *ListNode) *ListNode {
    var pre, record *ListNode
    for head != nil {
        record = head.Next
        head.Next = pre
        pre = head
        head = record
    }

    return pre
}

func addTwoNumbers(headA, headB *ListNode) *ListNode {
    headA, headB = reverseList(headA), reverseList(headB)
    // 虚拟头结点
    var YourHead *ListNode = &ListNode{Next: nil}
    cur := YourHead
    sum := 0

    for headA != nil || headB != nil || sum != 0 {
        if headA != nil {
            sum += headA.Val
            headA = headA.Next
        }
        if headB != nil {
            sum += headB.Val
            headB = headB.Next
        }
        cur.Next = &ListNode{Val: sum % 10}
        cur = cur.Next
        sum /= 10
    }

    return reverseList(YourHead.Next)
}

0 赞同 0 条回复

刺猬普通 2022年10月26日上午11:39

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode* head =nullptr;
        ListNode* l3 = nullptr;
        int k = 0;//进位标志
        while(l1 != nullptr || l2 != nullptr)
        {
            int n1 = l1 == nullptr ? 0 : l1->val;
            int n2 = l2 == nullptr ? 0 : l2->val;
            int sum = n1 + n2 + k;
            ListNode* node = new ListNode(sum % 10);
            if(head == nullptr)
                head = l3 = node;
            else
            {
                l3->next = node;
                l3 = l3->next;
            }
            k = sum >= 10 ? 1 : 0;
            if(l1)
                l1 = l1->next;
            if(l2)
                l2 = l2->next;      
        }
        if(k == 1)//最后判断是否仍有进位
        {
            l3->next = new ListNode(k);
        }
        head = reverseList(head);
        return head;
    }
public:
    ListNode* reverseList(ListNode* head) {//反转链表
        ListNode* temp;
        ListNode* H = nullptr;
        while(head != nullptr)
        {
            temp = head->next;
            head->next = H;
            H = head;
            head = temp;
        }
        return H;
    }
};

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

0 赞同 0 条回复

追普通 2022年10月26日上午11:16

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1),l2=reverse(l2);
        ListNode* head = new ListNode(-1);
        ListNode* p = head;
        int sum = 0; 
        while(l1||l2||){ //只要有一个不为空
            int s = sum; 
            if(l1) {s+=l1->val;    l1 = l1->next;}
            if(l2) {s+=l2->val;  l2 = l2->next}
            p->next = new ListNode(s%10); //定义新节点储存该位的值
            p = p->next; 
            sum = s/10; //得到进位
        }
        p->next = nullptr; //最后一个节点为nullptr，用于反转
        return reverse(head->next); //head为虚拟头节点

    }

    ListNode* reverse(ListNode* head){ //反转链表
        if(!head) return nullptr; //判断空链表情况
        ListNode* p = nullptr; //定义空节点为head的next
        ListNode*cur = head; //A-B-C-D ，移动当前节点p
        while(cur){ 
            ListNode* next = cur->next; //先储存cur下一个节点，再改变cur指向
            cur->next = p; //改变cur指向
            p=cur; //更新p和cur
            cur=next;
        }
        return p;
    }
};

先反转链表再进行相加操作，注意进位问题

0 赞同 0 条回复

Tolkien 永久会员 2022年10月26日上午12:02

方法一：反转链表再相加
1. 时间复杂度：O(max(n, m))
2. 空间复杂度：O(n+m)
3. 代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 1. 将链表倒序
        // 该节点用于存储最高位相加得到的进位
        ListNode forCarry = new ListNode(0);

        forCarry.next = l1;
        l1 = reverseList(forCarry);
        forCarry.next = l2;
        l2 = reverseList(forCarry);

        // 2. 遍历逆序后的链表，使两元素相加，将结果加入结果链表中
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead;
        boolean carry = false;

        while (l1 != null && l2 != null) {
            // 1. 判断前一位是否有进位，有进位则sum+1，反之则不变
            int sum = carry ? l1.val + l2.val + 1 : l1.val + l2.val;
            // 2. 若和大于等于10，sum减10，记录进位，反之则不变
            int num = sum >= 10 ? sum - 10 : sum;
            carry = sum >= 10;
            // 3. 让当前节点指向新的节点，其值为num
            temp.next = new ListNode(num);
            temp = temp.next;
            l1 = l1.next;
            l2 = l2.next;

            // 若其中一个链表位数少于另一链表，则为其补零
            if (l1 == null && l2 != null) {
                l1 = new ListNode(0);
            }
            if (l2 == null && l1 != null) {
                l2 = new ListNode(0);
            }
        }

        // 3. 若最高位无进位，则删除最开始补的0
        temp = dummyHead.next;
        while (temp.next.next != null) {
            temp = temp.next;
        }
        if (temp.next.val == 0) {
            temp.next = null;
        }

        return reverseList(dummyHead.next);
    }
    private ListNode reverseList(ListNode head) {
        // 1. 递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 2. 等价关系式
        ListNode newList = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newList;
    }
}

0 赞同 0 条回复

天然普通 2022年10月25日下午8:44

反转链表然后再相加，昨天想法是在原有长链表的基础上去添加元素，但无法解决创建多(>2)结点的问题，改变思路，重新建立一个新链表添加

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        def reverse(head):
            h = None
            p = None
            while head:
                h = head.next
                head.next = p
                p = head
                head = h
            return p
        if not l1:
            return l2
        if not l2:
            return l1 

        rone = reverse(l1)
        rTwo = reverse(l2)
        s = 0;
        dummy = ListNode(-1)
        cur = dummy

        while rone != None or rTwo != None:
            a = 0 if rone ==None else rone.val
            b = 0 if rTwo == None else rTwo.val 
            sum = a + b + s
            s = sum / 10
            cur.next = ListNode(sum % 10)
            cur = cur.next
            if rone != None:
                rone = rone.next;
            if rTwo != None:
                rTwo = rTwo.next



        if s > 0:
            cur.next = ListNode(s)

        return reverse(dummy.next)

0 赞同 0 条回复

Whatever 永久会员 2022年10月25日下午7:38

不知道对不对，先打卡一下

   public ListNode linkedListAdd(ListNode head1,ListNode head2){
        ListNode newHead1 = reverse(head1);
        ListNode newHead2 = reverse(head2);
        int add;
        ListNode cur = newHead1;
        while(newHead1 != null && newHead2 != null){
            int temp  = newHead1.val + newHead2.val;
            if(temp > 9){
                temp -= 10;
                add = 1;
                newHead1.val = temp;
                newHead1.next.val += 1;
            }else{
                newHead1.val = temp;
            }
            newHead1 = newHead1.next;
            newHead2 = newHead2.next;
        }
        ListNode res = reverse(cur);
        return res;
    }

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

0 赞同 0 条回复

@ 普通 2022年10月25日下午6:11

//思路：先翻转，在求和，再把结果进行翻转。
public class Solution {
    public ListNode linkedListAdd(ListNode head1, ListNode head2) {

        ListNode res = new ListNode();//用于返回结果的链表
        ListNode cur = res;
        ListNode h1 = reverseList(head1);//对head1进行翻转
        ListNode h2 = reverseList(head2);//对head2进行翻转
        int a = 0, b = 0;

        boolean isAdd = false;//用来判断是否进位

        while (h1 != null || h2 != null) {

            a = h1 == null ? 0 : h1.val;

            b = h2 == null ? 0 : h2.val;

            if (isAdd == false && a + b - 10 >= 0) {
                cur.val = (a + b) % 10;
                if (isAdd) cur.val += 1;

                isAdd = true;
            } else if (isAdd == true && a + b + 1 - 10 >= 0) {
                cur.val = (a + b + 1) % 10;

                isAdd = true;
            } else {
                cur.val = a + b;
                if (isAdd) cur.val += 1;
                isAdd = false;
            }

            if (h1 != null)
                h1 = h1.next;

            if (h2 != null)
                h2 = h2.next;

            if (h1 != null || h2 != null) {
                cur.next = new ListNode();
                cur = cur.next;
            }

        }

        //特殊处理 列如  head1 : 5 head2 : 5
        if (isAdd) {
            cur.next = new ListNode(1);

        }

        return reverseList(res);

    }

    //翻转链表
    public ListNode reverseList(ListNode head) {
        if (head == null)
            return null;

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

        ListNode res = reverseList(head.next);

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

        return res;

    }

}

0 赞同 0 条回复

Chin 普通 2022年10月25日下午4:31

class Solution {
     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);

        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            //  处理最后一位进位
            if (l1 == null && l2 == null) {
                cur.next = new ListNode(carry);
                break;
            }
            int l1Value = l1 == null ? 0 : l1.val;
            int l2Value = l2 == null ? 0 : l2.val;
            int value = l1Value + l2Value + carry;
            cur.next = new ListNode(value % 10);
            carry = value / 10;
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return reverse(dummyNode.next);
    }

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

https://leetcode.cn/problems/lMSNwu/
时间复杂度O(max(l1,l2))
空间复杂度O(1)

0 赞同 0 条回复

猫猫真可爱普通 2022年10月25日下午3:45

反转链表，然后遍历相加，注意进位。

class SolutionAdd {
    public ListNode  reverseList(ListNode node){
        ListNode pre = null;
        ListNode q= null;
        while (node != null) {
            q= node.next;
            node.next = pre;
            pre = node;
            node = q;
        }
        return pre;
    }
    public ListNode  addTwoNumbers(ListNode head1, ListNode head2) {
        ListNode listNode = new ListNode(0);
        ListNode p = listNode;
        int sum = 0;
        while (head1 != null || head2 != null || sum!=0) {
            if (head1 != null) {
                sum += head1.val;
                head1 = head1.next;
            }

            if (head1 != null) {
                sum += head1.val;
                head1 = head1.next;
            }
            p.next = new ListNode(sum % 10);
            sum = sum / 10;
            p = p.next;
        }
        return listNode.next;
    }
}

0 赞同 0 条回复

Asphyxia 普通 2022年10月25日下午2:46

见链接

/**
 * 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* reverse(ListNode* head){
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur!=nullptr){
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp; 
        }
        return pre;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* h1 = reverse(l1);
        ListNode* h2 = reverse(l2);
        int tag=0;
        ListNode* pre = nullptr;
        ListNode* ret = nullptr;
        while(h1!=nullptr||h2!=nullptr){
            int sum=0;
            if(h1!=nullptr){
                sum+=h1->val;
                h1=h1->next;
            }
            if(h2!=nullptr){
                sum+=h2->val;
                h2=h2->next;
            }
            sum+=tag;
            if(sum>=10){
                sum = sum%10;
                tag=1;
            }else{
                tag=0;
            }
            ret = new ListNode(sum,pre);
            pre = ret;
        }
        if(tag!=0){
            ret = new ListNode(tag,ret);
        }
        return ret;
    }
};

作者：pia7a
链接：https://leetcode.cn/problems/lMSNwu/solutions/1923336/lian-biao-zhong-de-liang-shu-xiang-jia-b-i0de/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

0 赞同 0 条回复

庄重普通 2022年10月25日下午1:49

 //进位的处理和最高位进位处理逻辑不太清晰
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* pTmp = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return pTmp;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr || l2 == nullptr) return l1 == nullptr ? l2 : l1;
        //反转l1 l2
        ListNode* pL1 = reverseList(l1);
        ListNode* pL2 = reverseList(l2);

        ListNode* dummy = new ListNode(0);
        ListNode* pCUr = dummy;
        int carry= 0;
        int val_l1 = 0,val_l2 = 0,sum = 0;
        while(pL1 != nullptr || pL2 != nullptr){
            val_l1 = pL1 == nullptr ? 0 : pL1->val;
            val_l2 = pL2 == nullptr ? 0 :pL2->val;
            sum = val_l1 + val_l2 + carry;
            carry = sum/10;

            pCUr->next = new ListNode(sum%10);
            pCUr = pCUr->next;
            if(pL1 != nullptr)
                pL1 = pL1->next;
            if(pL2 != nullptr)
                pL2 = pL2->next;
        }
        //边界处理
        if(carry > 0){
            pCUr->next = new ListNode(carry);
        }

        pCUr = reverseList(dummy->next);
        delete dummy;
        return pCUr;
    }
};
//时间复杂度O(n)
//空间复杂度O(n)

0 赞同 0 条回复

鸿渐普通 2022年10月25日下午1:42

  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
           //先将两个链表进行反转，然后低位相加 处理进位关系
        ListNode reverseList1 = reverseList(l1);
        ListNode reverseList2 = reverseList(l2);

        //设置一个虚拟节点
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        //然后开始相加

        //设置一个进位符号
        int carry = 0;
        while (reverseList1!=null||reverseList2!=null){
            int n1 = reverseList1==null?0:reverseList1.val;
            int n2 = reverseList2==null?0:reverseList2.val;
            int sum= n1+n2+carry;
            curr.next=new ListNode(sum%10);
            carry=sum/10;
            reverseList1=reverseList1==null?null:reverseList1.next;
            reverseList2=reverseList2==null?null:reverseList2.next;
            curr=curr.next;
        }
        // 如果上述循环结束后还有进位 则说明是高位进位

        if (carry==1){
            curr.next=new ListNode(1);
        }

        return reverseList(dummy.next);
    }

     public  ListNode reverseList(ListNode head) {
        //利用双指针法解决这个问题
        //初始化两个指针
        ListNode pre = null;
        ListNode curr = head;
        ListNode temp = null;

        while (curr != null) {
            // curr->next的值要被改变所以需要有一个临时变量来储存这个元素
            temp = curr.next;
            curr.next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月25日下午12:48

分析

定义一个逆序函数，该函数使用的递归，先将两个链表逆序，然后同位相加大于等于10，则进一位该位取余，别忘了特殊情况比如9944链表和链表56，最后进的一位再建立一个值为1的节点，然后连接上，最后再将相加后的链表逆序得到结果，具体详细见代码，时间空间复杂度都为O(n)。

代码

public class LinkedListAdd {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(9);
        ListNode l2 = new ListNode(9);
        ListNode l3 = new ListNode(4);
        ListNode l4 = new ListNode(4);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        ListNode l5 = new ListNode(5);
        ListNode l6 = new ListNode(6);
        l5.next = l6;
        ListNode listNode = linkedListAdd(l1, l5);
        System.out.println(listNode);
    }
    public static ListNode linkedListAdd(ListNode head1, ListNode head2){
        if(head1 ==null) return head2;
        if(head2 == null) return  head1;
        //先将两个链表反转
        ListNode headA1 = reverseLinkedList(head1);
        ListNode headA2 = reverseLinkedList(head2);
        System.out.println(headA1);
        System.out.println(headA2);
        int res = 0;
        ListNode headA3 = new ListNode(-1);
        ListNode resultA = headA3;
        while(headA1!=null&&headA2!=null){
            int k = headA1.val + headA2.val + res;
            ListNode temp = new ListNode( k% 10);
            if(k>=10){
                res = 1;
            }else {
                res = 0;
            }
            headA3.next = temp;
            headA3 = headA3.next;
            headA1 = headA1.next;
            headA2 = headA2.next;
        }

        while (headA1 != null){
            ListNode temp = new ListNode((headA1.val+ res) % 10);
            if(headA1.val+res>=10){
                res = 1;
            }else {
                res = 0;
            }
            headA3.next = temp;
            headA3 = headA3.next;
            headA1 = headA1.next;
        }
        while (headA2 != null){
            ListNode temp = new ListNode((headA2.val+ res) % 10);
            if(headA2.val+res>=10){
                res = 1;
            }else {
                res = 0;
            }
            headA3.next = temp;
            headA3 = headA3.next;
            headA2 = headA2.next;
        }
        if(res == 1){
            ListNode l1 = new ListNode(1);
            headA3.next = l1;
            headA3 = headA3.next;
        }
        System.out.println(resultA.next);
        ListNode listNode = reverseLinkedList(resultA.next);
        return listNode;
    }

    private static ListNode reverseLinkedList(ListNode head) {
        if(head.next==null){
            return head;
        }
        ListNode temp = reverseLinkedList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

0 赞同 0 条回复

派大星普通 2022年10月25日上午11:36

public class Solution8 {
//先将两个链表反转，然后再每位求和，考虑>9时的进位
//时间复杂度O(n)
//空间复杂度O(1)
    public ListNode linkedListAdd(ListNode head1, ListNode head2){
        if(head1 == null){
            return head2;
        } else if (head2 == null) {
            return head1;
        }
        while(head1 != null){

        }
        ListNode tempOne = head1;
        ListNode tempTwo = head2;
        ListNode preOne = null;
        ListNode preTwo = null;
        if(head1.next == null){
            preOne = tempOne;
        }else{
            while(tempOne != null){
                ListNode l = tempOne.next;
                tempOne.next = preOne;
                preOne = tempOne;
                tempOne = l;
            }
        }
        if(head2.next == null){
            preTwo = tempTwo;
        }else{
            while(tempTwo != null){
                ListNode l = tempTwo.next;
                tempTwo.next = preTwo;
                preTwo = tempTwo;
                tempTwo = l;
            }
        }
        while(preOne != null&&preTwo !=null){
            preOne.val += preTwo.val;
            if(preOne.val > 9){
                preOne.val = preOne.val % 10;
                if(preOne.next == null){
                    preOne.next = new ListNode(1);
                }else {
                    preOne.next.val++;
                }
            }
            preOne = preOne.next;
            preTwo = preTwo.next;
        }
        ListNode pre = null;
        while(preOne != null){
            ListNode l = preOne.next;
            preOne.next = pre;
            pre = preOne;
            preOne = l;
        }

        return pre;
    }
}

0 赞同 0 条回复

狗蛋儿普通 2022年10月25日上午11:30

思路：反转链表+链表加和+再反转

这个是比较麻烦的方式，最好的方式是将两个链表压入栈里。在栈里进行加法运算，最后再输出

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return nullptr;
        ListNode* temp;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    ListNode* addTwoNumbers1(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *ll1 = l1;
        ListNode *ll2 = l2;
        int l11 = 0,l22=0;
        while(ll1){
            l11++;
            ll1 =  ll1->next;
        }
        while(ll2){
            l22++;
            ll2 = ll2->next;
        }
        ll1 = l1;
        ll2 = l2;
        if(l22 > l11){
            swap(l22,l11);
            swap(ll1,ll2);
        }
        dummy->next=ll1;
        while(l22--){
            ll1->val += ll2->val;
            if(ll1->val >= 10){
                if(!ll1->next){
                    ListNode *tmp = new ListNode(1);
                    ll1->next = tmp;
                    ll1->val -= 10;
                }else{
                    ll1->next->val += 1;
                    ll1->val -= 10;
                }
            } 
            ll1 = ll1->next;
            ll2 = ll2->next;
        }
        while(ll1){
            if(ll1->val >= 10){

                ll1->val -= 10;
                if(!ll1->next){
                    ListNode *tmp = new ListNode(1);
                    ll1->next = tmp;
                }
                else ll1->next->val += 1;
            }
            ll1 = ll1->next;
        }
        return dummy->next;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* tmp1 = reverseList(l1);
        ListNode* tmp2 = reverseList(l2);
        return reverseList(addTwoNumbers1(tmp1,tmp2));
    }
};

0 赞同 0 条回复

小肸永久会员 2022年10月25日上午10:18

思路：先将两个链表反转，直接模拟，中间用一个int型carry记录前一位两个数相加是否产生进位，我是直接在链表1上直接修改，所以空间复杂度为O(1)，时间复杂度为O(n)。特殊输入:[[1],[9,9,9]]，[[5],[5]],[[9,1],[1,9]]。

public class Solution {
    public ListNode linkedListNode (ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        } else if (head2 == null) {
            return head1;
        }
        // 反转
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode res = head1;
        // 进位标志位
        int carry = 0;
        // 记录链表1的尾节点
        ListNode head1Tail = null;
        while (head1 != null && head2 != null) {
            int val = head1.val + head2.val + carry;
            carry = (val >= 10 ? 1 : 0);
            head1.val = val % 10;
            if (head1.next == null) {
                head1Tail = head1;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        // temp节点记录较长链表比较短链表多出来的那一段的第一个节点
        ListNode temp = null;
        // 两个链表长度一样，直接判断最后一次进位是否为1，由此判断是否在链表1的尾节点后面添加一个新的节点对应进位
        if (head1 == null && head2 == null) {
            if (carry == 1) {
                ListNode node = new ListNode(carry);
                head1Tail.next = node;
            }
            return reverse(res);
        }
        // 链表2比链表1长，temp指向链表2比链表1多出来的那段的第一个节点，并让head1Tail.next=temp
        else if (head1 == null) {
            temp = head2;
            head1Tail.next = temp;
        }
        // 链表1比链表2长，temp直接指向head1，因为链表1比链表2多出来的那段的第一个节点就是现在head1指向的节点
        else {
            temp = head1;
        }
        // 记录较长链表比较短链表多出来的那一段的尾节点
        ListNode tail = null;
        while (temp != null) {
            int val = temp.val + carry;
            carry = (val >= 10 ? 1 : 0);
            temp.val = val % 10;
            if (temp.next == null) {
                tail = temp;
            }
            temp = temp.next;
        }
        // 最后还有进位产生，需要添加一个新节点（比如list1:9->9->9，list2:1）
        if (carry == 1) {
            ListNode node = new ListNode(carry);
            tail.next = node;
        }
        return reverse(res);
    }
    private ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode node = cur.next;
            cur.next = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年10月25日上午10:05

先反转，然后sum存val值，tag标记有无标记为，因为加法，进位最多为1，所以tag = 0|| 1就行。

public static ListNode linkedListAdd(ListNode head1, ListNode head2) {
        head1 = resvers(head1);
        head2 = resvers(head2);
        ListNode cur = null;
        ListNode pre = null;
        int tag = 0;
        while (head1 != null || head2 != null) {
            int sum = 0;
            if (head1 != null) {
                sum+=head1.val;
                head1 = head1.next;
            }
            if (head2 != null) {
                sum+=head2.val;
                head2 = head2.next;
            }
            if (sum > 10) {
                sum = sum%10+tag;
                tag = 1;
            } else {
                tag = 0;
            }
            cur = new ListNode(sum,pre);
            pre = cur;
        }
        return cur;
    }

0 赞同 0 条回复

忆霁昕永久会员 2022年10月25日上午9:25

和两数相加思路基本一样，只是多了反转的操作
时间复杂度O(max{m,n}) 额外空间复杂度O(1)

class Solution {
    class ListNode {
        int val;
        ListNode next;
        public ListNode() {}
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode linkedListAdd(ListNode head1, ListNode head2){
        ListNode newHead1 = reverse(head1);
        ListNode newHead2 = reverse(head2);
        //4->3->2->1
        //4->3
        //控制进位
        int carry = 0;
        ListNode p1 = newHead1;
        ListNode p2 = newHead2;
        //结果链表
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;
        while (p1 != null || p2 != null) {
            int sum = 0;
            if (p1 != null) {
                sum += p1.val;
                p1 = p1.next;
            }
            if (p2 != null) {
                sum += p2.val;
                p2 = p2.next;
            }
            sum += carry;
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;
        }
        //如果还有进位 如9 + 9 = 18
        if (carry == 1) {
            tail.next = new ListNode(1);
            tail = tail.next;
        }

        //恢复
        reverse(newHead1);
        reverse(newHead2);
        return reverse(dummyHead.next);
    }
    private ListNode reverse(ListNode head) {
        ListNode newHead = null;
        //头插法
        ListNode p = head;
        while (p != null) {
            ListNode tmp = p.next;
            p.next = newHead;
            newHead = p;
            p = tmp;
        }
        return newHead;
    }
}

0 赞同 0 条回复

马啸天永久会员 2022年10月25日上午8:36

public class Solution {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(5);
        ListNode head2 = new ListNode(5);

        //计算的正式部分
        ListNode listNode = new Solution().linkedListAdd(head1 , head2);

        //输出部分
        while (listNode != null) {
            System.out.print(listNode.val);
            if (listNode.next != null) {
                System.out.print("->");
            }
            listNode = listNode.next;
        }
    }

    public ListNode linkedListAdd(ListNode head1 , ListNode head2) {
        //反转相加
        head1 = reverse(head1);
        head2 = reverse(head2);
        //用于存放结果
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        int sum = 0;
        int add = 0;//进位,初始为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;
            }
            //新建一个节点，值等于head1.val+head2.val + 前一个的进位
            cur.next = new ListNode((sum + add) % 10);
            cur = cur.next;
            //如果sum+add>=10  add=1
            if ((sum + add) >= 10)
                add = 1;
            else add = 0;
        }
        //最后如果没有节点了，但值>=10，还有进位，需要再创建一个节点
        if ((sum + add) >= 10) {
            cur.next = new ListNode(1);
            cur = cur.next;
        }

        //整体做反转
        ListNode reverse = reverse(dummyHead.next);
        return reverse;

    }

    //反转链表
    public ListNode reverse(ListNode head) {

        ListNode pre = null;
        ListNode cur = head;

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

}

0 赞同 0 条回复

Ruby🗽 普通 2022年10月25日上午12:42

public ListNode linkedListAdd(ListNode head1, ListNode head2){
        ListNode tou = reverse(head1);
        ListNode tou2 = reverse(head2);
        ListNode tou3 = new ListNode(0);
        ListNode biaoJi = tou3;
        //表示进位
        int q = 0;
        while (tou != null || tou2 != null){
            int a = tou == null ? 0 : tou.val;
            int b = tou2 == null ? 0 : tou2.val;
            int sum = a + b + q;
            q = sum / 10;
            biaoJi.next = new ListNode(q);
            biaoJi = biaoJi.next;
            tou = tou == null? null : tou.next;
            tou2 = tou2 == null? null : tou2.next;
        }
        if(q > 0) {
            biaoJi.next = new ListNode(q);
        }
        ListNode reverse = reverse(tou3);
        return reverse;
    }
    public ListNode reverse(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode tou = null;
        while (head.next != null){
            ListNode l1 = head.next;
            head.next = tou;
            tou = head;
            head = l1;
        }
        return tou;
    }

时间复杂度 n
空间复杂度 1

0 赞同 0 条回复

浅夏的无奈普通 2022年10月25日上午12:33

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

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverse(l1);
        l2 = reverse(l2);
        int add =0;
        ListNode head = new ListNode(-1);
        ListNode h = head;
        //将两个链表中的节点相加
        while(l1!=null||l2!=null){
            int sum = 0;
            if(l1!=null){
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                sum += l2.val;
                l2 = l2.next;
            }
            sum += add;
            add = sum /10;
            ListNode temp = new ListNode(sum%10);
            head.next = temp;
            head = head.next;
        }
        if(add!=0){
            ListNode temp = new ListNode(add);
            head.next = temp;
        }
        h.next = reverse(h.next);
        return h.next;
    }
    //反转链表
    public ListNode reverse(ListNode l){
        ListNode head = new ListNode(-1);
        ListNode h = head;
        ListNode cur = l;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = head.next;
            h.next = cur;
            cur = temp;
        }
        return h.next;
    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月25日上午12:11

解体方法：按照提示先进行反转，再进行加法计算，计算时分别考虑其中一个为空链表以及两链表长度不相等的情况，再将计算结果反转
时间复杂度：O(n)
空间复杂度：O(1)

class Solution:
    def linkedListAdd(self, head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
        # 反转链表
        head1 = self.reverse(head1)
        head2 = self.reverse(head2)

        # 反转链表相加
        added = 0
        while head1 or head2:
            res = ListNode(-1)
            s1 = head1.val if head1 else 0
            s2 = head2.val if head2 else 0
            val_sum = s1 + s2 + added
            if val_sum >= 10:
                added = val//10
            res.next = ListNode(val_sum%10)
            head1 = head1.next if head1 else None
            head2 = head2.next if head2 else None
        return self.reverse(res.next)

    def reverse(self,head:Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        prev,curr = None,head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

0 赞同 0 条回复

黎昕普通 2022年10月25日上午12:04

存在以下几种解法：
1. 逆转后相加再逆转回来
2. 使用栈（凡是逆序相关的题目均可以有意识地考虑）
3.遍历后获取两个length，然后将顺序对齐（快慢指针，慢指针指向上一个小于9的位置），这个解法比较复杂，但是情况并没有多少优化。

0 赞同 0 条回复

Error 普通 2022年10月24日下午11:10

class Node():
    def __init__(self, val = None, next = None):
        self.val = val
        self.next = next



def AddList(head1: Node, head2: Node):
    head1 = revers(head1)
    head2 = revers(head2)

    l1 = head1
    l2 = head2
    n = 0
    res = Node()
    cur = res
    while l1 or l2:
        c = n
        if l1:
            c += l1.val
            l1 = l1.next
        if l2:
            c += l2.val
            l2 = l2.next
        n = c // 10
        cur.next = Node(c % 10)
        cur = cur.next

    if n:
        cur.next = Node(n)

    return revers(res)


def revers(head: Node):
    pre = None
    while head:
        tmp = head.next
        head.next = pre
        pre = head
        head = tmp
    return pre

时间复杂度 O(n)

0 赞同 0 条回复

lone。普通 2022年10月24日下午10:49

class Solution {
    /**
        * @Description: 1.将链表翻转，从后往前计算
         *              2.当链表为null时，节点值为0
        */
    public ListNode linkedListAdd(ListNode head1, ListNode head2){
        if (head1 == null || head2 == null) {
            return null;
        }
        //翻转链表
        head1 = recur(head1);
        head2 = recur(head2);

        ListNode sum = null;

        while (head1 != null || head2 != null) {
            int a = head1 == null ? 0 : head1.val;
            int b = head2 == null ? 0 : head2.val;
            //建立链表头节点
            ListNode pre = new ListNode(a + b);
            //修改next引用指引
            pre.next = sum;
            //重新赋值链表
            sum = pre;
            head1 = head1 == null ? null : head1.next;
            head2 = head2 == null ? null : head2.next;
        }

        return sum;
    }

    /**
        * @Description: 迭代，双指针翻转链表
        */
    ListNode recur(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

时间复杂度O(N)

空间复杂度O(1) cur,pre使用额外空间

0 赞同 0 条回复

Gg 普通 2022年10月24日下午10:44

public ListNode add(ListNode head1,ListNode head2){
        // 先反转，再相加
        ListNode p1 = reverse(head1);
        ListNode p2 = reverse(head2);
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        while (p1 != null && p2 != null){
            int sum = p1.val + p2.val;
            if(sum-10 >= 0){
                // 大于10 添加两节点
                p.next = new ListNode(1);
                p = p.next;
                p.next = new ListNode(sum-10);
                p = p.next;
            }else{
                p.next = new ListNode(sum);
                p = p.next;
            }
        }
        // 再反转回来
        ListNode newHead = reverse(dummy.next);
        dummy.next = null;
        return newHead;

    }

    public ListNode reverse(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverse(head);
        head.next.next = head.next;
        head.next = null;
        return newHead;
    }

0 赞同 0 条回复

宁永久会员 2022年10月24日下午10:09

反转链表，操作相加，最后反转结果，自己测试了几个位数不同的，有进位的貌似都没有问题了。

public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    public ListNode linkedListAdd(ListNode head1, ListNode head2){
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        ListNode prev = null;
        boolean plus = false;
        while (cur1 != null || cur2 != null){
            if (cur1 == null){
                prev.next = new ListNode(cur2.val);
                cur1 = prev.next;
            } else {
                cur1.val = ( cur2 == null)? cur1.val : cur1.val + cur2.val;
            }
            if (plus){
                cur1.val = cur1.val + 1;
                plus = false;
            }
            if (cur1.val > 9){
                plus = true;
                cur1.val = cur1.val - 10;
            }
            prev = cur1;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        if (plus == true){
            prev.next = new ListNode(1);
        }
        head1 = reverseList(head1);
        return head1;
    }

0 赞同 0 条回复

T 普通 2022年10月24日下午10:04

下面代码

public class Day3Q1 {
  public ListNode linkedListAdd(ListNode one, ListNode two) {
    if(one == null || two == null) {
      return null;
    }
    //翻转链表1 和 链表2
    ListNode rOne = reverse(one), rTwo = reverse(two);
    // s记录进位， dummy用来记录新创建的节点
    int s = 0;
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    //循环加两个数组，当都遍历到null为止。
    while(rOne != null || rTwo != null) {
      int a = rOne == null ? 0 : rOne.val;
      int b = rTwo == null ? 0 : rTwo.val;
      int sum = a + b + s;
      s = sum / 10;
      cur.next = new ListNode(sum % 10);
      cur = cur.next;
      if(rOne != null) {
        rOne = rOne.next;
      }
      if(rTwo != null) {
        rTwo = rTwo.next;
      }
    }
    //循环结束如果还有进位，得再加一个节点，值为s。
    if(s > 0) {
      cur.next = new ListNode(s);
    }
    return reverse(dummy.next);
  }

  public ListNode reverse(ListNode head) {
    if(head == null) {
      return null;
    }
    ListNode cur = head, pre = null;
    while(cur != null) {
      ListNode tmp = cur.next;
      cur.next = pre;
      pre = cur;
      cur = tmp;
    }
    return pre;
  }
}

0 赞同 0 条回复

青木普通 2022年10月24日下午9:47

// - 用提示的思路做的，先将两个链表反转，我自己写了两个反转方法，
// 再依次进行相加，用hyper记录进位数
// - 踩坑：我数次把addNode进行反转，结果只返回一个节点，
// 这是因为addNode此时已经是为尾结点了，所以不行233333，
// 我还以为没连接上改了好多次写法，太菜了T T
// 时间复杂度O(n)
// 空间复杂度O(n) -递归反转
//          O(1) -双指针反转
class Solution {
    public ListNode reverseStr(ListNode head){
            if (head.next == null){
                return head;
            }
            ListNode node = reverseStr(head.next);
            head.next.next = head;
            head.next = null;

            return node;
    }

    public ListNode reverseStr2(ListNode head){
            if (head.next == null){
                return head;
            }

            ListNode pre = null;
            ListNode cur = head;

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

            return pre;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // ListNode n1 = reverseStr(l1);
        // ListNode n2 = reverseStr(l2);

        ListNode n1 = reverseStr2(l1);
        ListNode n2 = reverseStr2(l2);

        ListNode p1 = n1, p2 = n2;
        ListNode addNode = new ListNode((p1.val + p2.val) % 10);
        ListNode h = addNode;       
        int hyper = (p1.val + p2.val) / 10;
        p1 = p1.next;
        p2 = p2.next;

        while(p1 !=null && p2 != null){
            addNode.next = new ListNode((p1.val + p2.val + hyper) % 10);
            addNode = addNode.next;

            hyper = (p1.val + p2.val + hyper) / 10;

            p1 = p1.next;
            p2 = p2.next;
        }

        while(p2 != null){
            addNode.next = new ListNode((p2.val + hyper) % 10);
            addNode = addNode.next;

            hyper = (p2.val + hyper) / 10;

            p2 = p2.next;
        }

        while(p1 != null){
            addNode.next = new ListNode((p1.val + hyper) % 10);
            addNode = addNode.next;

            hyper = (p1.val + hyper) / 10;

            p1 = p1.next;
        }

        if(hyper != 0){
            addNode.next = new ListNode(hyper);
            addNode = addNode.next;      
        }

        // return reverseStr(h);
        return reverseStr2(h);
    }
}

0 赞同 0 条回复

🚲南下普通 2022年10月24日下午9:35

复杂度分析：
时间复杂度：O(max{m,n})，空间复杂度：O(1)

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverse(l1),l2=reverse(l2);
        ListNode* head = new ListNode(-1);
        ListNode* p = head;
        int carry = 0; //表示进位
        while(l1||l2||carry){ //只要有一个不为空
            int s = carry; 
            if(l1) s+=l1->val; //对应位相加
            if(l2) s+=l2->val;
            ListNode* q = new ListNode(s%10); //定义新节点储存该位的值
            p->next = q; //用于构建相加结果链表，移动p的位置
            p = p->next; 
            carry = s/10; //得到进位
            if(l1) l1=l1->next; //分别移动两个链表的节点
            if(l2) l2=l2->next;
        }
        p->next = nullptr; //最后一个节点为nullptr，用于反转
        return reverse(head->next); //head为虚拟头节点

    }

    ListNode* reverse(ListNode* head){ //反转链表
        if(!head) return nullptr; //判断空链表情况
        ListNode* p = nullptr; //定义空节点为head的next
        ListNode*cur = head; //A-B-C-D ，移动当前节点p
        while(cur){ 
            ListNode* next = cur->next; //先储存cur下一个节点，再改变cur指向
            cur->next = p; //改变cur指向
            p=cur; //更新p和cur
            cur=next;
        }
        return p;
    }
};

0 赞同 0 条回复

绍熙普通 2022年10月24日下午9:25

分析：
正常计算
1 2 3 4
3 4
1 2 6 8
思路结果
4 3 2 1
4 3
8 6 2 1
1 2 6 8
就是单向链表的翻转，然后进行计算，然后在翻转，即可得出答案

// 定义的单向基本链表结构
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
class SolutionAdd {
    //翻转方法，把单向链表翻转
    public ListNode fanzhuan(ListNode listNode){
        ListNode pre = null;
        ListNode succ = null;
        while (listNode != null) {
            succ = listNode.next;
            listNode.next = pre;
            pre = listNode;
            listNode = succ;
        }
        return pre;
    }
    //计算的单向链表求和
    public ListNode add(ListNode node1, ListNode node2) {
        ListNode listNode = new ListNode(0);
        ListNode p = listNode;
        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;
            }
            p.next = new ListNode(sum % 10);
            sum = sum / 10;
            p = p.next;
        }
        return listNode.next;
    }
}


public class Main {
    public static void main(String[] args) {
        //装载模拟数据 start
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        ListNode listNode5 = new ListNode(3);
        ListNode listNode6 = new ListNode(4);
        listNode5.next = listNode6;
        //装载模拟数据 end

        SolutionAdd solutionAdd = new SolutionAdd();
        //翻转链表listNode1
        ListNode fanzhuan = solutionAdd.fanzhuan(listNode1);
        //翻转链表listNode5
        ListNode fanzhuan1 = solutionAdd.fanzhuan(listNode5);
        //进行计算
        ListNode add = solutionAdd.add(fanzhuan, fanzhuan1);
        //再次翻转得到结果
        ListNode fanzhuan3 = solutionAdd.fanzhuan(add);
        //输出最后的单链表记录
        System.out.print(fanzhuan3.val);                //1
        System.out.print(fanzhuan3.next.val);           //2
        System.out.print(fanzhuan3.next.next.val);      //6
        System.out.print(fanzhuan3.next.next.next.val); //8
    }
}

0 赞同 0 条回复

易水寒永久会员 2022年10月24日下午9:18

反转链表

public ListNode linkedListAdd(ListNode head1, ListNode head2){
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        ListNode dummy = new ListNode();
        ListNode p1 = head1, p2 = head2, p = dummy;
        while(p1 != null && p2 != null) {
            p.next = new ListNode(p1.val+p2.val);
            p = p.next;
            p1 = p1.next;
            p2 = p2.next;
        }
        if(p1 != null) {
            p.next = p1;
        }
        else {
            p.next = p2;
        }
        return reverseList(dummy.next);
    }

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

0 赞同 0 条回复

波波_1936 普通 2022年10月24日下午9:00

    public ListNode linkedListAdd(ListNode head1, ListNode head2) {
        if (head1 == null) return head2;
        if (head2 == null) return head1;

        //步骤：1、先反转链表 2、操作相加 3、再反转结果
        ListNode r1 = reverseListNode(head1);
        ListNode r2 = reverseListNode(head2);

        boolean needCarry = false;//是否需要进位
        ListNode sum = new ListNode(-1);
        ListNode sumPre = sum;
        while (r1 != null || r2 != null) {
            int val = 0;
            int value1 = r1 == null ? 0 : r1.val;
            int value2 = r2 == null ? 0 : r2.val;
            val = value1 + value2;
            if (needCarry) {
                val++;
                needCarry = false;
            }
            if (val > 9) {
                needCarry = true;
                val = val % 10;
            }
            sum.next = new ListNode(val);
            sum = sum.next;
            if (r1 != null) {
                r1 = r1.next;
            }
            if (r2 != null) {
                r2 = r2.next;
            }
        }
        if (needCarry) {
            //最后一位进位
            sum.next = new ListNode(1);
        }
        return reverseListNode(sumPre.next);
    }
    //链表逆序
    private ListNode reverseListNode(ListNode listNode) {
        if (listNode == null || listNode.next == null) return listNode;
        ListNode pre = null;
        ListNode cu = listNode;
        while (cu != null) {
            ListNode next = cu.next;
            cu.next = pre;
            pre = cu;
            cu = next;
        }
        return pre;
    }

时间复杂度O(max(n,m))
空间复杂度O(1)

0 赞同 0 条回复

So 普通 2022年10月24日下午8:54

public ListNode linkedListAdd(ListNode head1, ListNode head2) {
        ListNode p1 = reverse(head1);
        ListNode p2 = reverse(head2);
        int tag = 0;
        ListNode pre = null;
        ListNode cur = null;
        while (p1 != null || p2 != null || tag != 0) {
            int a = 0;
            int b = 0;
            if (p1 != null) {
                a = p1.val;
                p1 = p1.next;
            }
            if (p2 != null) {
                b = p2.val;
                p2 = p2.next;
            }
            int sum = a + b + tag;
            if (sum > 9) {
                sum = sum % 10;
                tag = 1;
            } else {
                tag = 0;
            }
            cur = new ListNode(sum, pre);
            pre = cur;
        }
        return cur;
    }
    public ListNode reverse(ListNode head) {
        ListNode node = head;
        ListNode pre = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }

时间复杂度：O(max(m,n))，空间复杂度：O(1)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月24日下午8:12

对应解决的是力扣上的https://leetcode.cn/problems/lMSNwu/

//使用栈
//时间复杂度：O(max(M, N))，M 和 N 分别是链表 a 和 b 的长度；
//空间复杂度：O(M + N)，使用了两个栈
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while(l1 != null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        //设置进位
        int carry = 0;
        ListNode head = null;//为返回节点
        while(!stack1.isEmpty() || !stack2.isEmpty() || carry > 0){//即使栈都为空，还有进位的话还是需要创建一个节点
            int sum = carry;
            sum += stack1.isEmpty() ? 0 : stack1.pop();//不为空则弹出
            sum += stack2.isEmpty() ? 0 : stack2.pop();//不为空则弹出
            ListNode node = new ListNode(sum % 10);
            node.next = head;
            head = node;
            carry = sum / 10;
        }
        return head;
    }
}

反转链表

//反转链表
//时间复杂度O(N) 空间复杂度O(1)
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);//设置返回的虚拟节点
        ListNode cur = dummy;
        int carry = 0;
        l1 = reverse(l1);
        l2 = reverse(l2);
        //反转链表 变成02两数相加
        while(l1 != null || l2 != null || carry > 0){
            carry += l1 == null ? 0 : l1.val;
            carry += l2 == null ? 0 : l2.val;
            cur.next = new ListNode(carry % 10);
            cur = cur.next;
            carry /= 10;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return reverse(dummy.next);//翻转回来
    }
    public ListNode reverse(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

0 赞同 0 条回复

Y7n05h 普通 2022年10月24日下午7:41

当时只看到这一页，题目意思理解错了，现在修改一下，本题的题意和 leetcode https://leetcode.cn/problems/sum-lists-lcci/ 基本一致，除了这道 leetcode 中的链表默认已经翻转过。

class Solution {
public:
    static ListNode *_reverse(ListNode *head) {
        if (!head->next) return head;
        auto *backup = head->next;
        auto *ret = reverse(backup);
        backup->next = head;
        return ret;
    }
    static ListNode *reverse(ListNode *head) {
        auto *ret = _reverse(head);
        head->next = nullptr;
        return ret;
    }
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        unsigned int carry = 0;
        auto *res = l1;

        while (true) {
            carry += l1->val + l2->val;
            l1->val = carry % 10;
            carry = carry / 10;
            if (l1->next && l2->next) {
                l1 = l1->next;
                l2 = l2->next;
            } else
                break;
        }
        if (!l1->next && l2->next) {
            std::swap(l1->next, l2->next);
        }
        while (carry) {
            if (!l1->next) {
                l1->next = new ListNode(carry);
                return res;
            }
            l1 = l1->next;
            carry += l1->val;
            l1->val = carry % 10;
            carry /= 10;
        }
        return res;
    }
    ListNode *linkedListAdd(ListNode *l1, ListNode *l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        auto *ret = addTwoNumbers(reverse(l1), reverse(l2));
        return reverse(ret);
    }
};

0 赞同 1 条回复

shuaidi 永久会员 @ Y7n05h 2022年10月24日下午7:57

可以讲一下你的思路哦。

登录以回复

【体验面试】字节真题：单链表相加

代码参考

共以下 53 个回答

时间复杂度O(N)

空间复杂度O(N)

分析

代码

思路：反转链表+链表加和+再反转

# 回答此问题取消回复

【体验面试】字节真题：单链表相加

代码参考

共以下 53 个回答

时间复杂度O(N)

空间复杂度O(N)

分析

代码

思路：反转链表+链表加和+再反转

# 回答此问题 取消回复

# 回答此问题取消回复