21. Merge Two Sorted Lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5->\n"
     ]
    }
   ],
   "source": [
    "class ListNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "def mergeTwoLists (l1, l2):\n",
    "    if l1==None: return l2\n",
    "    if l2==None: return l1\n",
    "    dummy=ListNode(0)\n",
    "    p=dummy\n",
    "    p1=l1\n",
    "    p2=l2\n",
    "    while(p1 or p2):\n",
    "        if p1==None: \n",
    "            p.next=p2\n",
    "            break\n",
    "        if p2==None: \n",
    "            p.next=p1\n",
    "            break\n",
    "        if p1.val<p2.val:\n",
    "            p.next=p1\n",
    "            p1=p1.next\n",
    "        else:\n",
    "            p.next=p2\n",
    "            p2=p2.next\n",
    "        p=p.next\n",
    "    return dummy.next\n",
    "\n",
    "def printL(head):\n",
    "        p=head\n",
    "        s=''\n",
    "        while(p):\n",
    "            s=s+str(p.val)+'->'\n",
    "            p=p.next\n",
    "        print(s)\n",
    "        \n",
    "ln1=ListNode(1)\n",
    "ln2=ListNode(2)\n",
    "ln3=ListNode(3)\n",
    "ln4=ListNode(4)\n",
    "ln5=ListNode(5)\n",
    "\n",
    "ln1.next=ln3\n",
    "ln3.next=ln5\n",
    "ln2.next=ln4\n",
    "\n",
    "printL(mergeTwoLists(ln1,ln2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "]\n"
     ]
    }
   ],
   "source": [
    "s='[]()'\n",
    "print(s[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class ListNode(object):\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution(object):    \n",
    "    def mergeTwoLists (self,l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not l1:\n",
    "            return l2\n",
    "        if not l2:\n",
    "            return l1\n",
    "        p1=l1\n",
    "        p2=l2\n",
    "        if p1.val<=p2.val:\n",
    "            head=p1\n",
    "            p1=p1.next\n",
    "        else:\n",
    "            head=p2\n",
    "            p2=p2.next\n",
    "        p=head\n",
    "        while p1 or p2:\n",
    "            if not p1:\n",
    "                p.next=p2\n",
    "                return head\n",
    "            if not p2:\n",
    "                p.next=p1\n",
    "                return head\n",
    "            if p1.val<=p2.val:\n",
    "                p.next=p1\n",
    "                p1=p1.next\n",
    "                p=p.next\n",
    "            else:\n",
    "                p.next=p2\n",
    "                p2=p2.next            \n",
    "                p=p.next\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5->\n"
     ]
    }
   ],
   "source": [
    "def printL(head):\n",
    "        p=head\n",
    "        s=''\n",
    "        while(p):\n",
    "            s=s+str(p.val)+'->'\n",
    "            p=p.next\n",
    "        print(s)\n",
    "        \n",
    "ln1=ListNode(1)\n",
    "ln2=ListNode(2)\n",
    "ln3=ListNode(3)\n",
    "ln4=ListNode(4)\n",
    "ln5=ListNode(5)\n",
    "\n",
    "ln1.next=ln3\n",
    "ln3.next=ln5\n",
    "ln2.next=ln4\n",
    "s=Solution()\n",
    "printL(s.mergeTwoLists(ln1,ln2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}