讨论/《链表》 - 两数相加/
《链表》 - 两数相加
共 17 个回复
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return dummyHead.next;
    }
}
6

个人认为最容易理解的版本

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0,nullptr);
        ListNode* cur = head;
        int sum = 0;
         while(l1 || l2 || sum){
             if(l1){
                 sum += l1->val;
                 l1 = l1->next;
             }

             if(l2){
                 sum += l2->val;
                 l2 = l2->next;
             }

             cur->next = new ListNode(sum%10);
             cur = cur->next;
             sum /= 10;
         }
         return head->next;
    }
};
1

递归版本 很好理解 ans 是虚拟头结点 carry代表是否有进位

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    ans := &ListNode{
        -1,
        nil,
    }
    process(l1,l2,ans,0)
    return ans.Next
}

func process(l1,l2,ans *ListNode, carry int) {
    if l1 == nil && l2 == nil && carry == 0{
        return
    }else if (l1 == nil && l2 == nil && carry == 1) {
        cur := &ListNode{
            1,
            nil,
        }
        ans.Next = cur
        return
    }

    l1Digit ,l2Digit := 0, 0

    if l1 != nil {
        l1Digit = l1.Val
    }
    if l2 != nil {
        l2Digit = l2.Val
    }

    total := l1Digit + l2Digit + carry
    if total < 10 {
        cur := &ListNode{
            total,
            nil,
        }
        ans.Next = cur
        if l1 == nil {
            process(nil, l2.Next, cur, 0)
        }else if l2 == nil {
            process(l1.Next, nil, cur, 0)
        }else {
            process(l1.Next, l2.Next, cur, 0)
        }
    }else {
        cur := &ListNode{
            total % 10,
            nil,
        }
        ans.Next = cur
        if l1 == nil {
            process(nil, l2.Next, cur, 1)
        }else if l2 == nil {
            process(l1.Next, nil, cur, 1)
        }else {
            process(l1.Next, l2.Next, cur, 1)
        }
    }
}
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 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int tmp1Val = 0;
        int tmp2Val = 0;
        int tmpVal = 0;
        int carry = 0;
        ListNode tmpNode = new ListNode(-1);
        ListNode rNode = tmpNode;
        while(l1 != null || l2 != null) {
            tmp1Val = 0;
            tmp2Val = 0;
            if(l1 != null) {
                tmp1Val = l1.val;
            }
            if(l2 != null) {
                tmp2Val = l2.val;
            }
            tmpVal = tmp1Val+tmp2Val + carry;
            
            if((int)(tmpVal/10) > 0) {
                carry = 1;
                tmpVal = tmpVal%10;
            } else {
                carry = 0;
            }
            tmpNode.next = new ListNode(tmpVal);
            tmpNode = tmpNode.next;
            if(l1 != null) {
                l1 = l1.next;
            } else {
                l1 = null;
            }
            if(l2 != null) {
                l2 = l2.next;
            } else {
                l2 = null;
            }
        }

        if(carry == 1) {
            tmpNode.next = new ListNode(1);
        }
        return rNode.next;
    }
}
/**
 * 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) {
        StringBuilder builder1 = new StringBuilder();
        StringBuilder builder2 = new StringBuilder();    
        ListNode temp1 = l1;
        while(temp1 != null) {
            builder1.insert(0, String.valueOf(temp1.val));        
            temp1 = temp1.next;
        }
        ListNode temp2 = l2;
        while(temp2 != null) {
            builder2.insert(0, String.valueOf(temp2.val));        
            temp2 = temp2.next;
        }


        int resultVal = Integer.valueOf(builder1.toString()) + Integer.valueOf(builder2.toString());

 

        StringBuilder builder3 = new StringBuilder();
        builder3.append(String.valueOf(resultVal));
        builder3.reverse();

        String rStr = builder3.toString();
        
        

        ListNode tNode = null;
        int size = rStr.length();
        ArrayList<ListNode> nList = new ArrayList<>();
        for(int i=0; i<size;i++) {
            tNode = new ListNode(Integer.valueOf(String.valueOf(rStr.charAt(i))));
            nList.add(tNode);
        }

        int nSize = nList.size();
        for(int i=0; i<nSize;i++) {
            if(i+1 < nSize) {
                nList.get(i).next = nList.get(i+1);
            } else {
                nList.get(i).next = null;
            }
        }
        return nList.get(0);
    }
}

Customized Solution
image.png

/**
 * 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) {
        int size1=getLen(l1);
        int size2=getLen(l2);
        
        int stride=Math.min(size1,size2);
        ListNode dummy= size1 > size2 ? l1 : l2;
        ListNode res=dummy;
        ListNode head1=l1,head2=l2;
        int i=0;
        while(i<stride){
            int val =head1.val+head2.val;
            if(val>=10){
                dummy.val=val%10;
                if(dummy.next!=null){
                    dummy.next.val++;
                }else{
                    dummy.next=new ListNode(1);
                }
            }else{
                dummy.val=val;
            }
            dummy=dummy.next;
            head1=head1.next;
            head2=head2.next;
            i++;
        }

        
        while(dummy!=null&&dummy.next!=null){
            if(dummy.val>=10){
                dummy.val=dummy.val%10;
                dummy.next.val++;
            }
            dummy=dummy.next;
        }
        
        if(dummy==null){
            return res;
        }
        
        //check if incr the bits
        if(dummy.val>=10){
            dummy.val%=10;
            ListNode incr=new ListNode(1);
            dummy.next=incr;
        }
        
        return res;
        
        
    }
    
    private int getLen(ListNode head){
        int count=0;
        ListNode temp=head;
        while(temp!=null){
            count++;
            temp=temp.next;
        }
        
        return count;
    }
}

Python3

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        divdata = 0
        l3 = n = ListNode(0)
        if not l1:
            return l2
        if not l2:
            return l1
        while l1 or l2 or divdata:
            v1 = v2 = 0
            if l1 is not None:
                v1 = l1.val
                l1 = l1.next
            if l2 is not None:
                v2 = l2.val
                l2 = l2.next
            divdata, valdata = divmod(v1 + v2 + divdata,10)
            n.next = ListNode(valdata)
            n = n.next
        return l3.next
function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode(-1, null)
    let l3 = dummy
    let flag = 0

    while(l1 && l2) {
        const val = l1.val + l2.val + flag
        flag = Math.floor(val / 10)
        l3.next = new ListNode(val % 10, null)
        l3 = l3.next
        l1 = l1.next
        l2 = l2.next
        if (!l1 && !l2) {
            break
        }
        if (!l1) {
            l1 = new ListNode(0, null)
        }
        if (!l2) {
            l2 = new ListNode(0, null)
        }
    }
    if (flag) {
        l3.next = new ListNode(flag, null)
    }
    return dummy.next
};

看错了题目,看成了高位在前,低位在后,绕了个弯写的是头插法还多写了链表的原地转置😂。
基础还是不行,原地转置又花了挺多时间,这里做个记录。(和本题没有什么联系,仅作一次记录)
假设传入的头节点为head
1、定义节点newHead用于记录转置后的头节点,初始化为null;
2、依次遍历链表的每一个节点pos,头插法的过程如下:

// while 循环
newHead = NULL;
while(head!=NULL){
    pos=head;
    head = head->next;
    pos->next = newHead;
    newHead = pos;
}
// for 循环
newHead = NULL;
for(pos = head; pos!=NULL; pos = head){
    head = head->next;
    pos->next = newHead;
    newHead = pos;
}

嘻嘻,我自己写出来的,看了下和官方也不一样

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);
        ListNode head = prehead;
        int lastVal = 0;
        while(l1 != null || l2 != null) {
            int val = lastVal;
            if(l1 != null) {
                val += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                val += l2.val;
                l2 = l2.next;
            } 
            if(val > 9) {
                val = val - 10;
                lastVal = 1;
            } else {
                lastVal = 0;
            }
            head.next = new ListNode(val);
            head = head.next;  
        }
        if(lastVal > 0) {
            head.next = new ListNode(lastVal);
        }
        return prehead.next;

    }
}