Groking The coding Interview

滑动窗口

AddTwoNumbers
You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题报告

理解题意

• 2 个 非空链表，长度可能不相等
• 每个链表为逆序
• 返回两个链表的和
• 每个元素应该为正数

理解例子

• 2 -> 4 -> 3 = 342
• 5 -> 6 -> 4 = 465
• 342 + 465 = 807
• 答案 : 7 -> 0 -> 8

思路

• 将每一个链表变成整形，然后相加，结果分解成链表不大合适，还得处理越界的情况
• 比较合理的办法：是一边遍历一边生成链表
• 每一个生成的节点为两个数的和，有可能产生进位: 如 7+8=15
• 一个节点的结果为：sum = 前一个节点的进位+两个节点的和，res = sum % 10;
• 一个节点的结果几种情况
  • last_carry + left + right < 10
  • last_carry + left + right >= 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) return l2;
        if (!l2) return l1;

        int carry = 0;
        ListNode dummy(0);
        ListNode *head = &dummy;
        while (l1 || l2 || carry) {
            int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
            head->next = new ListNode (sum % 10);
            head = head->next;
            carry = sum / 10;

            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }

        return dummy.next;
    }
};

public class ListNode {
 public var val: Int
 public var next: ListNode?
 public init(_ val: Int) {
     self.val = val
     self.next = nil
 }
}

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    	var l1 = l1
        var l2 = l2
        var prev = ListNode(0)
        var carry = 0
        let head = prev

        while l1 != nil || l2 != nil || carry != 0 {
            let cur = ListNode(0)
            let sum = (l2 == nil ? 0 : l2!.val) + (l1 == nil ? 0 : l1!.val) + carry
            cur.val = sum % 10
            carry = sum / 10
            prev.next = cur
            prev = cur
            l1 = l1 == nil ? l1: l1?.next
            l2 = l2 == nil ? l2: l2?.next
        }

        return head.next
    }
}

递归

这道题比较简单，递归模式也比较好想到
加法需要三个值，两个操作符（来自两个链表）以及一个进位标记。
因此递归模式为：

• 递归出口：两个链表都已经到达末尾，并且没有进位
• 递归实现：
  • 当前节点的结果为：和/10
  • 当前节点的next节点为：对于两个链表next节点的计算的结果

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry) {
        if (!l1 && !l2 && !carry) return nullptr;
        int sum = (l1?l1->val:0) + (l2?l2->val:0) + carry;
        ListNode *ans = new ListNode(sum % 10);
        ans->next = addTwoNumbers(l1?l1->next:nullptr, l2?l2->next:nullptr, sum / 10);
        return ans;
    }
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return addTwoNumbers(l1, l2, 0);
    }
};

时间复杂度

遍历次数：max(len(l1), len(l2)) + 1，因此是线性时间 \(\mathcal{O(max(len(l1), len(l2)))}\)

空间复杂度

额外申请了和一个链表，因此空间复杂度也为 \(\mathcal{O(max(len(l1), len(l2)))}\)