LeetCode程式設計題——add-two-numbers

題目描述

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

題意：給出兩個表示兩個非負數的連結清單。這些數字以相反的順序存儲，每個節點都包含一個數字。添加兩個數字并将其作為連結清單傳回。

題目分析

我了解的題意是給出的連結清單的值都是非負數，如果兩個數相加大于10 需要進位的話就向連結清單的後一個節點進位（這就是題目說的數字以相反的順序存儲），例如，輸入是 (2 -> 4 -> 3) + (8 -> 6 -> 4) 那麼輸出應該是 0 -> 1 -> 8 ；因為2+8需要向下一個節點進 1 ，4+6+1=11 需要向下一個節點進1 ，最後一個節點位置為 3+4+1=8 。大緻解題思路：

• 先考慮兩個連結清單分别為空的情況——則直接傳回另外一個連結清單；
• 當連結清單不為空時，設定一個臨時變量temp存放兩個連結清單的和值，再建立一個新的連結清單來存放輸對外連結表，存放的值為temp%10
• 當連結清單1、連結清單2或temp不為0時進行循環，temp/=10
• 最後輸出輸對外連結表的值

代碼實作

/**
 * 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) {
        //判斷兩個連結清單為空的情況
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        //至少有一個連結清單不為空
        int temp=0;
        ListNode *head=new ListNode(0);
        ListNode *p=head;
        while(l1 != NULL || l2 !=NULL || temp !=0)
        {
            if(l1 != NULL)
            {
                temp=temp+l1->val;
                l1=l1->next;
            }
            if(l2 != NULL)
            {
                temp=temp+l2->val;
                l2=l2->next;
            }
            p->next=new ListNode(temp%10);
            p=p->next;
            temp=temp/10;
        }
        return head->next;
    }
};