【leetcode】两数相加【中等】(C++递归解法）

总体来说，链表类问题往往是蛮适合用递归的方式求解的

要写出有效的递归，关键是要考虑清楚：

0. return的条件

1. 每步递归的操作，以及何时调用下一步递归

2. 鲁棒性（头，尾结点等特殊情况是否依旧成立）

题目见下

结构体定义

struct ListNode//在c++定义结构体时，typedef不是必须的 { 	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 { private: 	int k = 0; //用来记录进位 public:     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {     	if(l1 == nullptr && l2 == nullptr) 		{ 			if(k == 1) 			{ 				ListNode* t_node = new ListNode(1); 				return t_node; 			} 			else return nullptr; 		} 		else if(l1 == nullptr) 		{ 			l2->val += k; 			if(l2->val != 10)  return l2; 			else{ 				k = 1; 				l2->next = addTwoNumbers(l1, l2->next); 				l2->val = 0; 				return l2; 			} 		}        		else if(l2 == nullptr) 		{ 			l1->val += k;   			if(l1->val != 10)  return l1; 			else{ 				k = 1; 				l1->val = 0; 				l1->next = addTwoNumbers(l1->next, l2); 				return l1; 			} 		} 		else{ 			l1->val += (l2->val + k); 			if(l1->val >= 10) 			{ 				l1->val %= 10; 				k = 1; 			} 			else k = 0; 			l1->next = addTwoNumbers(l1->next, l2->next); 			return l1; 		}       } };  

~希望对你有启发~