LeetCode 445. 两数相加 II

ゞ浴缸里的玫瑰 2023-07-25 09:40 32阅读 0赞

### 解题思路 ###

无需逆转链表。两次dfs即可  
第一次，需要计算出两个链表的长度。  
第二次，回溯过程中，直接进行相加计算。

这个要求对回溯有很好的理解。

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode *tmp1 = l1;
            ListNode *tmp2 = l2;
            int len1= getLen(tmp1);
            int len2  = getLen(tmp2);
            int flag= 0;
            ListNode *ans= NULL;
            if(len2>len1)
            {
                dfs(l2,l1,flag,ans,len2,len1);
            }
            else
            {
                dfs(l1,l2,flag,ans,len1,len2);
            }
            if(flag)
            {
                ListNode *tmp = new ListNode(flag);
                ListNode *tt =ans;
                tmp->next = tt;
                ans = tmp;
            }
            return ans;
        }
        int getLen(ListNode* l1)
        {
            int ans=0;
            while(l1)
            {
                l1= l1->next;
                ans++;
            }
            return ans;
        }
        void dfs(ListNode* l1, ListNode* l2,int &flag,ListNode * &ans,int len1,int len2)
        {
            if(len1==0||len2==0)
            {
                return;
            }
            //cout<<len1<<" "<<len2<<endl;
            if(len1>len2)
            {
                int t_len = len1-1;
                dfs(l1->next,l2,flag,ans,t_len,len2);
            }
            else if(len2>len1)
            {
                int t_len = len2-1;
                dfs(l1,l2->next,flag,ans,len1,t_len);
            }
            else
            {
                dfs(l1->next,l2->next,flag,ans,--len1,--len2);
            }
            if(len1==len2)
            {
                ListNode *tmp = new ListNode(0);
                ListNode *tmp1 = ans;
                tmp->val = (l1->val+l2->val+flag)%10;
                flag =  (l1->val+l2->val+flag)/10;
                tmp->next = tmp1;
                ans = tmp;
            }
            else
            {
                ListNode *tmp = new ListNode(0);
                ListNode *tmp1 = ans;
                tmp->val = (l1->val+flag)%10;
                flag =  (l1->val+flag)/10;
                tmp->next = tmp1;
                ans = tmp;
            }
        }
    };