solution_python/021 Merge Two Sorted Lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 021 Merge Two Sorted Lists\n",
    "- 笔记作者：CV七少\n",
    "- 学习时间：2020.7.1\n",
    "- 编程语言：python\n",
    "- 学习任务：leetcode题解\n",
    "- 题目地址：https://leetcode-cn.com/problems/merge-two-sorted-lists/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题目:\n",
    "将两个升序链表合并为一个新的` 升序 `链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 示例：\n",
    "- 示例 1:\n",
    "    ```\n",
    "    输入：1->2->4, 1->3->4\n",
    "    输出：1->1->2->3->4->4\n",
    "    ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 题解"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法一：**</font> 递归  [题解](https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/yi-kan-jiu-hui-yi-xie-jiu-fei-xiang-jie-di-gui-by-/)\n",
    "```\n",
    "执行用时：56 ms, 在所有 Python3 提交中击败了18.41%的用户\n",
    "内存消耗：13.7 MB, 在所有 Python3 提交中击败了7.14%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为：1->1->2->3->4->4\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 mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        if l1 and l2:\n",
    "            if l1.val > l2.val: l1, l2 = l2, l1\n",
    "            l1.next = self.mergeTwoLists(l1.next, l2)\n",
    "        return l1 or l2\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:    l1:1->2->4  l2:1->3->4\n",
    "               output:    1->1->2->3->4->4\n",
    "\"\"\"\n",
    "l1 = ListNode(1)\n",
    "l1.next = ListNode(2)\n",
    "l1.next.next = ListNode(4)\n",
    "l2 = ListNode(1)\n",
    "l2.next = ListNode(3)\n",
    "l2.next.next = ListNode(4)\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.mergeTwoLists(l1, l2)\n",
    "print('输出为：%d->%d->%d->%d->%d->%d' % \\\n",
    "      (result.val, result.next.val, result.next.next.val, result.next.next.next.val,\\\n",
    "      result.next.next.next.next.val, result.next.next.next.next.next.val))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=#008000>**方法二：**</font> 递循环遍历  [题解](https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/xin-shou-you-hao-xue-hui-tao-lu-bu-fan-cuo-4nian-l/)\n",
    "```\n",
    "执行用时：44 ms, 在所有 Python3 提交中击败了79.61%的用户\n",
    "内存消耗：13.8 MB, 在所有 Python3 提交中击败了7.14%的用户\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "输出为：1->1->2->3->4->4\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 mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        move = dummy\n",
    "        while l1 and l2:\n",
    "            if l1.val <= l2.val:\n",
    "                move.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                move.next = l2\n",
    "                l2 = l2.next\n",
    "            move = move.next\n",
    "        move.next = l1 if l1 else l2\n",
    "        return dummy.next\n",
    "\n",
    "\"\"\"\n",
    "For Example:    input:    l1:1->2->4  l2:1->3->4\n",
    "               output:    1->1->2->3->4->4\n",
    "\"\"\"\n",
    "l1 = ListNode(1)\n",
    "l1.next = ListNode(2)\n",
    "l1.next.next = ListNode(4)\n",
    "l2 = ListNode(1)\n",
    "l2.next = ListNode(3)\n",
    "l2.next.next = ListNode(4)\n",
    "                \n",
    "solution = Solution()\n",
    "result = solution.mergeTwoLists(l1, l2)\n",
    "print('输出为：%d->%d->%d->%d->%d->%d' % \\\n",
    "      (result.val, result.next.val, result.next.next.val, result.next.next.next.val,\\\n",
    "      result.next.next.next.next.val, result.next.next.next.next.next.val))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考\n",
    "1. https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/yi-kan-jiu-hui-yi-xie-jiu-fei-xiang-jie-di-gui-by-/\n",
    "2. https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/xin-shou-you-hao-xue-hui-tao-lu-bu-fan-cuo-4nian-l/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 如果你觉得有用的话：\n",
    "- 请点点 **star** 呦\n",
    "- 关注我的 [CSDN博客](https://mp.csdn.net/console/article)\n",
    "- 关注我的 [哔哩哔哩](https://space.bilibili.com/424394389/channel/detail?cid=132513)\n",
    "- 关注公众号：CV伴读社\n",
    "<img src='./images/qrcode.jpg' style='zoom:100%'>"
   ]
  }
 ],
 "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.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}