题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

题解

这道题目比较简单，从前到后遍历两个链表，对应位置上的数字相加，同时注意进位即可。具体地：

• 当前位置相加后的结果需要取余10。
• 当前位置不仅要加两个数，还要加上前一步的进位值。
• 若当前位置相加后大于10，要向后进位。
• 可能最后计算出的结果会多出来一位。

这里的一个技巧是，在具体实现时，可以借助递归。

代码

Python

# 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 dfs(self,l1,l2,flag):
        if l1 is None and l2 is None:
            return None if flag==0 else ListNode(1)
        if l2 is None:
            return ListNode((l1.val+flag)%10,self.dfs(l1.next,None,(l1.val+flag)//10))
        if l1 is None:
            return ListNode((l2.val+flag)%10,self.dfs(None,l2.next,(l2.val+flag)//10))
        return ListNode((l1.val+l2.val+flag)%10,self.dfs(l1.next,l2.next,(l1.val+l2.val+flag)//10))
        
    def addTwoNumbers(self, l1, l2):
        return self.dfs(l1,l2,0)

这里使用了递归，借助了ListNode的初始化方法，传入当前的值与之后的指针。dfs方法每次返回一个指针。

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	ListNode curr1=l1,curr2=l2;
    	boolean flag=false;
    	ListNode list=new ListNode((curr1.val+curr2.val)%10);
    	ListNode curr3=list;
    	if(curr1.val+curr2.val>=10) 
    		flag=true;
    	while(curr1.next!=null&&curr2.next!=null) {
    		curr1=curr1.next;
    		curr2=curr2.next;
    		if(flag==true) {
    			curr3.next=new ListNode((curr1.val+curr2.val+1)%10);
    			if(curr1.val+curr2.val+1>=10)
    				flag=true;
    			else
    				flag=false;
    		} else {
    			curr3.next=new ListNode((curr1.val+curr2.val)%10);
    			if(curr1.val+curr2.val>=10)
    				flag=true;
    			else
    				flag=false;
    		}
    		curr3=curr3.next;
    	}
    	while(curr1.next!=null) {
    		curr1=curr1.next;
    		if(flag==true) {
    			curr3.next=new ListNode((curr1.val+1)%10);
    			if(curr1.val+1>=10)
    				flag=true;
    			else
    				flag=false;
    		} else {
    			curr3.next=new ListNode((curr1.val)%10);
    			flag=false;
    		}
    		curr3=curr3.next;
    	}
    	while(curr2.next!=null) {
    		curr2=curr2.next;
    		if(flag==true) {
    			curr3.next=new ListNode((curr2.val+1)%10);
    			if(curr2.val+1>=10)
    				flag=true;
    			else
    				flag=false;
    		} else {
    			curr3.next=new ListNode((curr2.val)%10);
    			flag=false;
    		}
    		curr3=curr3.next;
    	}
        if(flag==true) {
            curr3.next=new ListNode(1);
            curr3=curr3.next;
        }
    	curr3.next=null;
    	return list;
    }
}

Java代码是两年前写的了，没有使用递归，直接一步步计算、多层判断的，可能有些冗长，有较多的待优化的地方。因为以后基本不用Java了，所以在这里就不改进了，仅供参考算法流程。

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
	public:
		ListNode* dfs(ListNode* l1, ListNode* l2, int flag) {
			if(l1==nullptr and l2==nullptr) {
				if(flag) return new ListNode(flag);
				return nullptr;
			} else if(l1==nullptr) {
				return new ListNode((l2->val+flag)%10, dfs(l1, l2->next, (l2->val+flag)/10));
			} else if(l2==nullptr) {
				return new ListNode((l1->val+flag)%10, dfs(l1->next, l2, (l1->val+flag)/10));
			} else {
				return new ListNode((l1->val+l2->val+flag)%10, dfs(l1->next, l2->next, (l1->val+l2->val+flag)/10));
			}
		}

		ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
	 		return dfs(l1, l2, 0);
		}
};