lintcode-221-链表求和 II

221-链表求和 II

假定用一个链表表示两个数，其中每个节点仅包含一个数字。假设这两个数的数字顺序排列，请设计一种方法将两个数相加，并将其结果表现为链表的形式。

样例

给出 6->1->7 + 2->9->5。即，617 + 295。

返回 9->1->2。即，912 。

标签

链表 高精度

思路

利用 LintCode-35.翻转链表 和 lintcode-167-链表求和 的代码，将链表逆序后求和，之后将结果再次逆序

code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /*
     * @param l1: The first list.
     * @param l2: The second list.
     * @return: the sum list of l1 and l2.
     */
    ListNode * addLists2(ListNode * l1, ListNode * l2) {
        // write your code here
        l1 = reverse(l1);
        l2 = reverse(l2);
        return reverse(addLists(l1, l2));
    }    ListNode *reverse(ListNode *head) {
        // write your code here
        ListNode *l1 = NULL, *l2 = NULL, *l3 = NULL;        l1 = head;
        //  链表没有节点或有一个节点
        if (l1 == NULL || l1->next == NULL) {
            return l1;
        }
        l2 = l1->next;
        //  链表有2节点
        if (l2->next == NULL) {
            l2->next = l1;
            l1->next = NULL;
            return l2;
        }
        l3 = l2->next;
        //  链表有3个以上节点
        if (l2->next != NULL) {
            while (l2 != l3) {
                l2->next = l1;
                if (l1 == head)
                    l1->next = NULL;
                l1 = l2;
                l2 = l3;                if (l3->next != NULL)
                    l3 = l3->next;
            }
            l2->next = l1;
            return l2;
        }
    }     ListNode *addLists(ListNode *l1, ListNode *l2) {
        // write your code here
        ListNode *head = new ListNode(0);
        ListNode *temp = head;
        int carry = 0;
        while (l1 != NULL && l2 != NULL) {
            int sum = l1->val + l2->val + carry;
            ListNode *node = new ListNode(sum % 10);
            carry = (sum >= 10);
            temp->next = node;
            l1 = l1->next;
            l2 = l2->next;
            temp = temp->next;
        }
        while (l1 != NULL) {
            int sum = l1->val + carry;
            ListNode *node = new ListNode(sum % 10);
            carry = (sum >= 10);
            temp->next = node;
            l1 = l1->next;
            temp = temp->next;
        }
        while (l2 != NULL) {
            int sum = l2->val + carry;
            ListNode *node = new ListNode(sum % 10);
            carry = (sum >= 10);
            temp->next = node;
            l2 = l2->next;
            temp = temp->next;
        }
        if (l1 == NULL && l2 == NULL && carry == 1) {
            ListNode *node = new ListNode(carry);
            temp->next = node;
        }
        return head->next;
    }
};