Leetcode|445.两数相加 II Leetcode|DFS

题目描述 ??给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
??你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
??如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例

【Leetcode|445.两数相加 II】输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

思路 dfs。参考：leetcode中文社区
解法

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: pair dfs(ListNode* l1, ListNode* l2, int d1, int d2) { if (l1 == nullptr || l2 == nullptr) { return {NULL, 0}; } pair p; int val = 0; if (d1 == d2) { p = dfs(l1->next, l2->next, d1 - 1, d2 - 1); val = p.second + l1->val + l2->val; } else if (d1 > d2) { p = dfs(l1->next, l2, d1 - 1, d2); val = p.second + l1->val; } else { p = dfs(l1, l2->next, d1, d2 - 1); val = p.second + l2->val; } auto node = new ListNode(val % 10); node->next = p.first; return {node, val / 10}; }int depth(ListNode* l) { int d = 0; while (l != NULL) { ++d; l = l->next; } return d; }ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int d1 = depth(l1); int d2 = depth(l2); auto p = dfs(l1, l2, d1, d2); if (p.second > 0) { auto node = new ListNode(p.second); node->next = p.first; return node; } return p.first; } };