题目
描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9 要求：空间复杂度 O(n)，时间复杂度 O(n)
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
示例 1
输入：[9,3,7],[6,3]返回值：{1,0,0,0}说明：如题面解释
复制代码
示例 2
备注：
1≤n,m≤1060≤ai,bi≤9
分析
考虑特殊情况
在进行问题分析过程前，我们先考虑一下特殊情况，那么在这道问题中，有哪些情况是特殊的呢？
不难发现，如下情况：
考虑一般情况
首先我们可以看到题目中描述的链表中的数据是从高位到低位的，但是我们正常的加法运算都是从低往高位进行计算的，所以我们可以考虑先将链表进行反转，然后再做处理。
在我们做加法运算时，可以考虑以哪一个链表作为主链表，基于这样一个原因，两个 n 位数相加，最多会生成一个 n+1 位数，所以我们可以将较长的链表作为主链表，并增加一个 pReturn 节点。
使用两个指针同时访问这两个链表，然后做加法，并进行进位操作，依次操作，最后如果进位还有标志，那就需要增加一个节点保存多余的一位信息。
由于我们使用了较长的链表作为返回信息的主要组成部分，所以在空间上面复杂度可以达到 O(1)
前面的计算信息是链表逆序的，这里我们还需要将结果链表再反过来。
如果 pReturn 节点的值为 0，那就返回 pReturn->next;
如果 pReturn 节点的值为 1，那就返回 pReturn.
题解中参考的处理步骤：
step 1：任意一个链表为空，返回另一个链表就行了，因为链表为空相当于 0，0 加任何数为 0，包括另一个加数为 0 的情况。
step 2：相继反转两个待相加的链表，反转过程可以参考反转链表。
step 3：设置返回链表的链表头，设置进位 carry=0.
step 4：从头开始遍历两个链表，直到两个链表节点都为空且 carry 也不为 1. 每次取出不为空的链表节点值，为空就设置为 0，将两个数字与 carry 相加，然后查看是否进位，将进位后的结果（对 10 取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历。
注意：这里增加了新的节点，所以空间复杂度是 O(n)的。
代码示例
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here if (nullptr == head1) { return head2; } if (nullptr == head2) { return head1; }
// the head point ListNode* pReturn = new ListNode(0); ListNode* pQuick = nullptr; ListNode* pSlow = nullptr; ListNode* pLong = nullptr;
// reverse list int length1 = GetLinkListLength(head1); int length2 = GetLinkListLength(head2); ListNode* pReverse1 = ReverseLinkList(head1); ListNode* pReverse2 = ReverseLinkList(head2); pQuick = pReverse1; pLong = pReverse1; pSlow = pReverse2; if (length2 > length1) { pLong = pReverse2; pQuick = pReverse2; pSlow = pReverse1; }
int entry = 0; ListNode* pPre = nullptr; while (nullptr != pSlow || nullptr != pQuick) { int SlowVal = nullptr == pSlow ? 0 : pSlow->val;
pQuick->val += SlowVal + entry; entry = pQuick->val/10; pQuick->val %= 10;
pPre = pQuick; pQuick = pQuick->next; pSlow = nullptr == pSlow ? nullptr : pSlow->next; } pPre->next = pReturn; pReturn->val = entry;
pReturn = ReverseLinkList(pLong); if (pReturn->val == 1) { return pReturn; } else { return pReturn->next; } }
int GetLinkListLength(ListNode* head) { int length = 0; while (nullptr != head) { length++; head = head->next; } return length; }
ListNode* ReverseLinkList(ListNode* head) { if (nullptr == head || nullptr == head->next) { return head; }
ListNode* pPre = nullptr; ListNode* pCur = head; ListNode* pNext = head->next;
while (nullptr != pCur) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; } return pPre; }};
复制代码
评论