LeetCode题目笔记——面试题 02.05. 链表求和

题目描述

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

题目链接

题目难度——中等

方法一：模拟

  按照题目的意思，如果链表是从地位开始走的话，那就好办了，我们只需要模拟一下做加法就行，需要注意的是进位的跟踪。

代码/C++

/**
 * 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 *res = new ListNode, *cur = res;
        int carry = 0, tmp;
        ListNode *p1 = l1, *p2 = l2;
        while(p1 != NULL && p2 != NULL){
            tmp = p1->val + p2->val + carry;
            cur->next = new ListNode(tmp % 10);
            carry = tmp > 9 ? 1 : 0;
            cur = cur->next;
            p1 = p1->next;
            p2 = p2->next;
        }
        while(p1 != NULL){
            cur->next = new ListNode((p1->val + carry) % 10);
            cur = cur->next;
            carry = p1->val + carry > 9 ? 1 : 0;
            p1 = p1->next;
        }
        while(p2 != NULL){
            cur->next = new ListNode((p2->val + carry) % 10);
            cur = cur->next;
            carry = p2->val + carry > 9 ? 1 : 0;
            p2 = p2->next;
        }
        if(carry){
            cur->next = new ListNode(1);
        }
        return res->next;
    }
};

  代码有点长，还可以精简一下，比如把后面两个循环和最后的判断carry都放到以第一个循环里去，这里用python再写一次。

代码/Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 模拟
        res = ListNode(-1)
        head = res
        carry = 0
        while l1 != None or l2 != None or carry:
            tmp = 0
            tmp += l1.val if l1 else 0
            tmp += l2.val if l2 else 0
            tmp += carry
            res.next = ListNode(tmp % 10)
            carry = 1 if tmp > 9 else 0
            res = res.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        
        return head.next

方法二——递归

  还可以用递归来解决，递归函数接收4个参数，分别是两个链表和结果链表以及进位，在递归体内当进位和两个链表指针都为空的时候就开始“归”，只要还有一个不为空，就继续往下递，在递的过程中进行加法。

代码/C++

/**
 * 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 *res = new ListNode(-1);
        int carry = 0;
        sum(l1, l2, carry, res);
        return res->next;
    }

    void sum(ListNode *l1, ListNode *l2, int carry, ListNode *res){
        if (l1 == NULL && l2 == NULL && carry == 0){
            return ;
        }
        int tmp = 0;
        tmp += l1 == NULL ? 0 : l1->val;
        tmp += l2 == NULL ? 0 : l2->val;
        tmp += carry;
        res->next = new ListNode(tmp % 10);
        carry = tmp > 9 ? 1 : 0;
        sum(l1 == NULL ? NULL : l1->next, l2 == NULL ? NULL : l2->next, carry, res->next);
    }
};

进阶——借用栈或者先反转原链表

  进阶思考的链表按照我们人更易读的数位顺序存储数据，但处理起来更麻烦了，我们可以借用一个栈来表示这个先用低位的关系，将两个链表元素都入栈之后，就可以用前面两种方法来做了。

/**
 * 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) {
        // 进阶问题，用栈解决，或者先翻转一下链表，再用之前的方法
        stack<int> stack1, stack2, stackres;
        ListNode *p1 = l1, *p2 = l2, *res = new ListNode(-1), *p = res;
        while(p1){
            stack1.push(p1->val);
            p1 = p1->next;
        }
        while(p2){
            stack2.push(p2->val);
            p2 = p2->next;
        }
        int carry = 0, tmp;
        while(!stack1.empty() || !stack2.empty() || carry){
            tmp = 0;
            tmp += stack1.empty() ? 0 : stack1.top();
            tmp += stack2.empty() ? 0 : stack2.top();
            if(!stack1.empty()) stack1.pop();
            if(!stack2.empty()) stack2.pop();
            tmp += carry;
            stackres.push(tmp % 10);
            carry = tmp > 9 ? 1 : 0;
        }
        while(!stackres.empty()){
            p->next = new ListNode(stackres.top());
            stackres.pop();
            p = p->next;
        }
        return res->next;
    }

};

总结

  几种方法都要遍历一遍链表，所以时间是O(N)，用到了栈的话空间就是O(N)。