docs/Algorithm/Leetcode/Python/002._add_two_numbers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2.Add Two Numbers\n",
    "\n",
    "### 难度：Medium\n",
    "\n",
    "## 刷题内容：\n",
    "\n",
    "> 原题链接：\n",
    "\n",
    " - 中文：https://leetcode-cn.com/problems/add-two-numbers
    " - 英文：https://leetcode.com/problems/add-two-numbers/\n",
    "\n",
    "> 内容描述：\n",
    "\n",
    "给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。\n",
    "\n",
    "你可以假设除了数字 0 之外，这两个数字都不会以零开头。\n",
    "\n",
    "示例：\n",
    "```\n",
    "输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)\n",
    "输出：7 -> 0 -> 8\n",
    "原因：342 + 465 = 807\n",
    "```\n",
    "\n",
    "## 解法方案\n",
    "\n",
    "由于两数相加可能会出现进位，所以加法我们谁都会算，但是要着重注意的一点是，要考虑上一位的进位，并且传递给下一位计算时的进位。\n",
    "\n",
    "> 思路 1\n",
    "\n",
    "我们先构建一个空的头结点不动，然后尾结点从头结点开始向后不断生成新的结点。遍历两个链表的公共部分，每次相加相应位数字和进位，分配到结果的链表中。公共部分遍历完后再确定长的链表剩余的部分，同样的方式遍历完。\n",
    "\n",
    " - 需要注意的是遍历时每次都要更新进位，不断计算和时有没有发生进位，以防止之前数据的污染。\n",
    " - 对于 python 来说，需要新的变量做游标来遍历两个链表，不能直接用形参，否则我们会修改原链表。\n",
    " - 注意最后可能的进位。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "0\n",
      "8\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:     \n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        # 用 p1, p2 赋值为 l1 和 l2 ，以防止我们的操作改变原链表\n",
    "        p1, p2 = l1, l2\n",
    "        # 创建一个空链表用来返回结果，分别有头结点和尾结点\n",
    "        head = ListNode(0)\n",
    "        tail = head\n",
    "        # carry 表示进位值\n",
    "        carry = 0\n",
    "        # 处理两个链表的公共部分，也就是两个链表都不为空的部分\n",
    "        while p1 and p2:\n",
    "            # 计算当前位相加的和\n",
    "            num = p1.val + p2.val + carry\n",
    "            # 大于 9 ，应该向前进一位\n",
    "            if num > 9:\n",
    "                num -= 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            # 添加结点\n",
    "            tail.next = ListNode(num)\n",
    "            # 尾结点向后移动\n",
    "            tail = tail.next\n",
    "            # 移动两条链表的公共部分\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "        # 取长链表剩余的部分，也就是未参与上面计算的部分\n",
    "        if p2:\n",
    "            # 如果 p2 较长，将 p2 剩余的部分赋值给 p1 ，我们只需要处理 p1 就行了\n",
    "            p1 = p2\n",
    "        # 接下来，处理长链表剩余分部分\n",
    "        while p1:\n",
    "            # 最近的一位，我们要考虑一下，是否有进位\n",
    "            num = p1.val + carry\n",
    "            if num > 9:\n",
    "                num -= 10\n",
    "                carry = 1\n",
    "            else:\n",
    "                carry = 0\n",
    "            # 添加结点\n",
    "            tail.next = ListNode(num)\n",
    "            tail = tail.next\n",
    "            \n",
    "            # 移动我们处理的链表\n",
    "            p1 = p1.next\n",
    "        # 如果最后仍然有进位，我们需要再分配一个结点\n",
    "        if carry:\n",
    "            # 创建一个 val 为 1 的 ListNode 结点，然后将 tail 向后移动一位\n",
    "            tail.next = ListNode(1)\n",
    "            tail = tail.next\n",
    "        # 将所有的加和及进位都处理完成了，现在我们将链表收尾\n",
    "        tail.next = None\n",
    "        # 将 链表的头结点返回\n",
    "        return head.next # 去除掉我们初始化为 0 的头结点\n",
    "\n",
    "la = ListNode(2)\n",
    "la.next = ListNode(4)\n",
    "la.next.next = ListNode(3)\n",
    "\n",
    "lb = ListNode(5)\n",
    "lb.next = ListNode(6)\n",
    "lb.next.next = ListNode(4)\n",
    "\n",
    "s = Solution()\n",
    "ss = s.addTwoNumbers(la, lb)\n",
    "print(ss.val)\n",
    "print(ss.next.val)\n",
    "print(ss.next.next.val)\n",
    "print(ss.next.next.next) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因此，这个地方我们可以考虑使用递归来求解，具体可以分为以下情况：\n",
    "\n",
    " - 当两个链表均不为空时，计算两个节点值与上一位进位的和 sum，取 sum 的个位数构建新的节点，更新进位为 sum 的十位数，令本节点的 next 指针指向下一位求和返回的节点。\n",
    " - 当两个链表其中一个为空时，计算不为空的节点值与上一位进位的和 sum，更新进位为 sum 的十位数。若进位不为 0 ，取 sum 的个位数构建新节点，令本节点的 next 指针指向下一位求和返回的节点，注意只传递不为空的链表；若进位为 0，则直接更新不为空节点的值为 sum，此时此链表之后的所有高位值都不会更新，因此返回此节点。\n",
    " - 若两个链表都为空，判断进位是否为 0。若进位为 0，直接返回 NULL；否则构建值为进位值的新节点，并返回此节点。\n",
    " \n",
    "> 思路 2\n",
    "\n",
    " - 跟 plus One ，add Binary 玩的同一个花样，但是相对上个思路来说，更加简单和简洁。\n",
    " - 使用递归调用简化算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "0\n",
      "8\n",
      "None\n"
     ]
    }
   ],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution(object):\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        # 特殊情况\n",
    "        if l1 == None:\n",
    "            return l2\n",
    "        if l2 == None:\n",
    "            return l1\n",
    "        # 如果 相加 小于 10 ，不需要进位\n",
    "        if l1.val + l2.val < 10:\n",
    "            l3 = ListNode(l1.val + l2.val)\n",
    "            l3.next = self.addTwoNumbers(l1.next, l2.next)\n",
    "        # 相加大于等于 10，需要进位\n",
    "        elif l1.val + l2.val >= 10:\n",
    "            l3 = ListNode(l1.val + l2.val - 10)\n",
    "            tmp = ListNode(1)\n",
    "            tmp.next = None\n",
    "            # 递归调用\n",
    "            l3.next = self.addTwoNumbers(l1.next, self.addTwoNumbers(l2.next ,tmp))\n",
    "        return l3\n",
    "    \n",
    "la = ListNode(2)\n",
    "la.next = ListNode(4)\n",
    "la.next.next = ListNode(3)\n",
    "\n",
    "lb = ListNode(5)\n",
    "lb.next = ListNode(6)\n",
    "lb.next.next = ListNode(4)\n",
    "\n",
    "s = Solution()\n",
    "ss = s.addTwoNumbers(la, lb)\n",
    "print(ss.val)\n",
    "print(ss.next.val)\n",
    "print(ss.next.next.val)\n",
    "print(ss.next.next.next)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}