LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 对于链表问题，通常可以在头节点之前加上一个 dummy 节点，这样遍历链表时头节点与其他节点是等价的，易于以统一形式处理，返回时将 dummy 节点的下一节点作为返回值即可。对于遍历到空指针的情况，视为值为 0 即可以统一形式处理

class Solution {
 public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    if (!l1) {
      return l2;
    }
    if (!l2) {
      return l1;
    }
    ListNode* p = l1;
    ListNode* q = l2;
    ListNode* dummy = new ListNode(-1);  // 任意值均可，无实际作用，习惯 -1
    ListNode* cur = dummy;
    int carry = 0;
    while (p || q) {
      int a = p ? p->val : 0;
      int b = q ? q->val : 0;
      int sum = a + b + carry;
      carry = sum / 10;
      sum = sum % 10;
      cur->next = new ListNode(sum);
      cur = cur->next;
      if (p) {
        p = p->next;
      }
      if (q) {
        q = q->next;
      }
    }
    if (carry == 1) {
      cur->next = new ListNode(1);
    }
    return dummy->next;
  }
};

• 递归形式

class Solution {
 public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    return addTwoNumbersImpl(l1, l2, 0);
  }

  ListNode* addTwoNumbersImpl(ListNode* l1, ListNode* l2, int t) {
    if (!l1) {
      if (!l2) {
        return t == 0 ? nullptr : new ListNode(t);
      }
      l2->val += t;
      if (l2->val < 10) {
        return l2;
      }
      int carry = l2->val / 10;
      l2->val %= 10;
      l2->next = addTwoNumbersImpl(nullptr, l2->next, carry);
      return l2;
    }
    if (!l2) {
      return addTwoNumbersImpl(l2, l1, t);
    }
    ListNode* res = new ListNode;
    int sum = l1->val + l2->val + t;
    res->val = sum % 10;
    res->next = addTwoNumbersImpl(l1->next, l2->next, sum / 10);
    return res;
  }
};