{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution Notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: Delete a node in the middle, given only access to that node.\n",
    "\n",
    "* [Constraints](#Constraints)\n",
    "* [Test Cases](#Test-Cases)\n",
    "* [Algorithm](#Algorithm)\n",
    "* [Code](#Code)\n",
    "* [Unit Test](#Unit-Test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraints\n",
    "\n",
    "* Can we assume this is a non-circular, singly linked list?\n",
    "    * Yes\n",
    "* What if the final node is being deleted, do we make it a dummy with value None?\n",
    "    * Yes\n",
    "* Can we assume we already have a linked list class that can be used for this problem?\n",
    "    * Yes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases\n",
    "\n",
    "* Delete on empty list -> None\n",
    "* Delete None -> None\n",
    "* Delete on one node -> [None]\n",
    "* Delete on multiple nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm\n",
    "\n",
    "We'll need two pointers, one to the current node and one to the next node.  We will copy the next node's data to the current node's data (effectively deleting the current node) and update the current node's next pointer.\n",
    "\n",
    "* set curr.data to next.data\n",
    "* set curr.next to next.next\n",
    "\n",
    "Complexity:\n",
    "* Time: O(1)\n",
    "* Space: O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%run ../linked_list/linked_list.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyLinkedList(LinkedList):\n",
    "\n",
    "    def delete_node(self, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        if node.next is None:\n",
    "            node.data = None\n",
    "        else:\n",
    "            node.data = node.next.data\n",
    "            node.next = node.next.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unit Test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting test_delete_mid.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile test_delete_mid.py\n",
    "import unittest\n",
    "\n",
    "\n",
    "class TestDeleteNode(unittest.TestCase):\n",
    "\n",
    "    def test_delete_node(self):\n",
    "        print('Test: Empty list, null node to delete')\n",
    "        linked_list = MyLinkedList(None)\n",
    "        linked_list.delete_node(None)\n",
    "        self.assertEqual(linked_list.get_all_data(), [])\n",
    "\n",
    "        print('Test: One node')\n",
    "        head = Node(2)\n",
    "        linked_list = MyLinkedList(head)\n",
    "        linked_list.delete_node(head)\n",
    "        self.assertEqual(linked_list.get_all_data(), [None])\n",
    "\n",
    "        print('Test: Multiple nodes')\n",
    "        linked_list = MyLinkedList(None)\n",
    "        node0 = linked_list.insert_to_front(2)\n",
    "        node1 = linked_list.insert_to_front(3)\n",
    "        node2 = linked_list.insert_to_front(4)\n",
    "        node3 = linked_list.insert_to_front(1)\n",
    "        linked_list.delete_node(node1)\n",
    "        self.assertEqual(linked_list.get_all_data(), [1, 4, 2])\n",
    "\n",
    "        print('Test: Multiple nodes, delete last element')\n",
    "        linked_list = MyLinkedList(None)\n",
    "        node0 = linked_list.insert_to_front(2)\n",
    "        node1 = linked_list.insert_to_front(3)\n",
    "        node2 = linked_list.insert_to_front(4)\n",
    "        node3 = linked_list.insert_to_front(1)\n",
    "        linked_list.delete_node(node0)\n",
    "        self.assertEqual(linked_list.get_all_data(), [1, 4, 3, None])\n",
    "\n",
    "        print('Success: test_delete_node')\n",
    "\n",
    "\n",
    "def main():\n",
    "    test = TestDeleteNode()\n",
    "    test.test_delete_node()\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Test: Empty list, null node to delete\n",
      "Test: One node\n",
      "Test: Multiple nodes\n",
      "Test: Multiple nodes, delete last element\n",
      "Success: test_delete_node\n"
     ]
    }
   ],
   "source": [
    "%run -i test_delete_mid.py"
   ]
  }
 ],
 "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.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}