03-Linked-Lists.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3.0 Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Add some common functions for representing linked lists and converting between linked lists and python lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListNode(object):\n",
    "    \"\"\"Node in a singly linked list.\"\"\"\n",
    "    \n",
    "    def __init__(self, data, next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "\n",
    "        \n",
    "def make_linked_list(elems):\n",
    "    \"\"\"Return a linked list initialized from python list.\"\"\"\n",
    "    head, node = None, None\n",
    "    for elem in elems:\n",
    "        if head is None:\n",
    "            head = ListNode(elem)\n",
    "            node = head\n",
    "        else:\n",
    "            node.next = ListNode(elem)\n",
    "            node = node.next\n",
    "    return head\n",
    "\n",
    "\n",
    "def make_list(head):\n",
    "    \"\"\"Return a python list initialized from linked list.\"\"\"\n",
    "    elems, node = [], head\n",
    "    while node is not None:\n",
    "        elems.append(node.data)\n",
    "        node = node.next\n",
    "    return elems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.1 Reverse a linked list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Statement\n",
    "Reverse the nodes of a linked list without using any additional storage."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_reverse_list (__main__.ReverseListTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.004s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7f0ad8102dd8>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "import unittest\n",
    "\n",
    "\n",
    "def reverse_list(head):\n",
    "    \"\"\"Reverse the singly linked list in-place.\"\"\"\n",
    "    node = head\n",
    "    while node.next is not None:\n",
    "        tmp = node.next\n",
    "        node.next = node.next.next  # Bypass current next.\n",
    "        tmp.next = head  # Make next the new head.\n",
    "        head = tmp\n",
    "    return head\n",
    "\n",
    "\n",
    "class ReverseListTest(unittest.TestCase):\n",
    "\n",
    "    def test_reverse_list(self):\n",
    "        case = collections.namedtuple('case', ['input','expected'])\n",
    "        cases = [\n",
    "            case([1,2,3,4], [4,3,2,1]),\n",
    "            case([1], [1]),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            in_list = make_linked_list(c.input)\n",
    "            rev_list = reverse_list(in_list)\n",
    "            self.assertEqual(make_list(rev_list), c.expected)\n",
    "\n",
    "\n",
    "unittest.main(ReverseListTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.2 Implement grade school addition using lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Statement\n",
    "Implement grade school addition for two numbers represented as lists of digits from `0-9` with the **least** significant digit appearing first."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_sum_digits (__main__.SumDigitsTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.005s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7f0ad8085ba8>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "import unittest\n",
    "\n",
    "\n",
    "def sum_digits(a, b):\n",
    "    \"\"\"Compute sum of a and b represented as digits in linked list.\"\"\"\n",
    "    head, node, nodea, nodeb, carry = None, None, a, b, 0\n",
    "    while nodea is not None or nodeb is not None:\n",
    "        # Add the digits.\n",
    "        digita = 0 if nodea is None else nodea.data\n",
    "        digitb = 0 if nodeb is None else nodeb.data\n",
    "        sumdigits = digita + digitb + carry\n",
    "        if sumdigits > 9:\n",
    "            carry = sumdigits // 10  # Round toward zero.\n",
    "            sumdigits = sumdigits % 10\n",
    "        # Append the digits to the sum.\n",
    "        if head is None:\n",
    "            head = ListNode(sumdigits)\n",
    "            node = head\n",
    "        else:\n",
    "            node.next = ListNode(sumdigits)\n",
    "            node = node.next\n",
    "        # Advance the pointers.\n",
    "        nodea = None if nodea is None else nodea.next\n",
    "        nodeb = None if nodeb is None else nodeb.next\n",
    "        \n",
    "    # Handle any remaining carry digits.\n",
    "    if carry > 0:\n",
    "        node.next = ListNode(carry)\n",
    "\n",
    "    return head\n",
    "    \n",
    "\n",
    "class SumDigitsTest(unittest.TestCase):\n",
    "\n",
    "    def test_sum_digits(self):\n",
    "        case = collections.namedtuple('case', ['a','b','expected'])\n",
    "        cases = [\n",
    "            # One-digit, no carry.\n",
    "            case([0],[0], [0]),\n",
    "            case([1],[2], [3]),\n",
    "            # One-digit, carry.\n",
    "            case([6],[4], [0,1]),\n",
    "            case([5],[6], [1,1]),\n",
    "            # Two-digit, no carry.\n",
    "            case([2,1],[4,3], [6,4]),\n",
    "            # Two-digit, carry.\n",
    "            case([1,6],[8,8], [9,4,1]),\n",
    "            # Mix of unequal number of digits.\n",
    "            case([3,1],[5], [8,1]),\n",
    "            case([2,1],[0,2,3], [2,3,3]),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            a, b = make_linked_list(c.a), make_linked_list(c.b)\n",
    "            sum_ab = sum_digits(a, b)\n",
    "            self.assertEqual(make_list(sum_ab), c.expected)\n",
    "\n",
    "\n",
    "unittest.main(SumDigitsTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3 Rearrange a linked list to alternate low-high"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Statement\n",
    "Implement a function that given a list of integers in any order, returns the list with values arranged in alternating sequence of low followed by high.\n",
    "\n",
    "#### Examples\n",
    "```\n",
    "input:  [1,2,3,4,5]\n",
    "output: [1,3,2,5,4]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_low_high (__main__.LowHighTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.011s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7f0ad80a5390>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "import unittest\n",
    "\n",
    "\n",
    "def low_high(head):\n",
    "    \"\"\"Rearrange nodes of singly linked list into alternating low-high.\"\"\"\n",
    "    assert not(head.next is None), 'invalid: list requires >= 2 nodes'\n",
    "\n",
    "    # Partition the list using two pointers.\n",
    "    # p1 and p2 point to adjacent pairs of nodes.\n",
    "    # p1_low is toggled to maintain the alternating low-high sequence. \n",
    "    p1, p2, p1_low = head, head.next, True\n",
    "    while p2 is not None:\n",
    "        # Swap data when invariant is violated.\n",
    "        if p1_low and not(p1.data < p2.data):\n",
    "            p1.data, p2.data = p2.data, p1.data\n",
    "        elif not(p1_low) and p1.data < p2.data:\n",
    "            p1.data, p2.data = p2.data, p1.data\n",
    "        p1, p2, p1_low = p2, p2.next, not(p1_low)\n",
    "\n",
    "\n",
    "class LowHighTest(unittest.TestCase):\n",
    "\n",
    "    def test_low_high(self):\n",
    "        case = collections.namedtuple('case', ['input','expected'])\n",
    "        cases = [\n",
    "            # Sorted ascending order.\n",
    "            case([1,2,3,4,5], [1,3,2,5,4]),\n",
    "            # Sorted descending order.\n",
    "            case([5,4,3,2,1], [4,5,2,3,1]),\n",
    "            # Ascending order concatenated with descending order.\n",
    "            case([1,2,3,3,2,1], [1,3,2,3,1,2]),\n",
    "            # Descending order concatenated with ascending order.\n",
    "            case([3,2,1,1,2,3,], [2,3,1,2,1,3]),\n",
    "            # No swaps required.\n",
    "            case([1,3,2,5,4], [1,3,2,5,4]),\n",
    "            # Random.\n",
    "            case([1,4,9,2,7,5,3,8,6], [1,9,2,7,4,5,3,8,6]),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            ll = make_linked_list(c.input)\n",
    "            low_high(ll)\n",
    "            self.assertEqual(make_list(ll), c.expected)\n",
    "\n",
    "\n",
    "unittest.main(LowHighTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.4 Overlapping lists without cycles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Problem Statement\n",
    "Given two acyclic lists of size $m$ and $n$, determine whether the lists overlap with each other and return the first overlapping node, if any. \n",
    "\n",
    "#### Clarification\n",
    "For this problem, lists overlap when the last $p$ nodes ($p \\leq m$ and $p \\leq n$) are common between the lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "test_list_overlap (__main__.ListOverlapTest) ... ok\n",
      "\n",
      "----------------------------------------------------------------------\n",
      "Ran 1 test in 0.003s\n",
      "\n",
      "OK\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<unittest.main.TestProgram at 0x7f0ad807b6d8>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import collections\n",
    "import unittest\n",
    "\n",
    "\n",
    "def list_length(head):\n",
    "    \"\"\"Return the length of a linked list.\"\"\"\n",
    "    node, length = head, 0\n",
    "    while node is not None:\n",
    "        length += 1\n",
    "        node = node.next\n",
    "    return length\n",
    "\n",
    "\n",
    "def list_overlap(a, b):\n",
    "    \"\"\"Return first overlapping node, if any, between linked lists.\"\"\"\n",
    "    # Compute the length of each list.\n",
    "    m, n = list_length(a), list_length(b)\n",
    "    \n",
    "    # Advance the longer list by the difference in size, if any.\n",
    "    nodea, nodeb, diff = a, b, abs(m-n)\n",
    "    if m > n:\n",
    "        while diff > 0:\n",
    "            nodea = nodea.next\n",
    "            diff -= 1\n",
    "    elif m < n:\n",
    "        while diff > 0:\n",
    "            nodeb = nodeb.next\n",
    "            diff -= 1\n",
    "    \n",
    "    # Advance the nodes in tandem until overlapping nodes are found.\n",
    "    while not(nodea is None) and not(nodeb is None):\n",
    "        if nodea == nodeb:\n",
    "            break\n",
    "        nodea, nodeb = nodea.next, nodeb.next\n",
    "    \n",
    "    return nodea  # Returns None if no overlap found.\n",
    "\n",
    "\n",
    "class ListOverlapTest(unittest.TestCase):\n",
    "    \n",
    "    def setUp(self):\n",
    "        self.listA = make_linked_list([1,2,3])\n",
    "        self.listB = make_linked_list([4,5,6,7,8])\n",
    "        self.listC = make_linked_list([9,10,11,12])\n",
    "        # Create a list C and append A.\n",
    "        self.listCUA = make_linked_list(make_list(self.listC))\n",
    "        node = self.listCUA\n",
    "        while node.next is not None:\n",
    "            node = node.next\n",
    "        node.next = self.listA\n",
    "\n",
    "    def test_list_overlap(self):\n",
    "        case = collections.namedtuple('case', ['a','b','expected'])\n",
    "        cases = [\n",
    "            # No overlap.\n",
    "            case(self.listA, self.listB, None),\n",
    "            case(self.listB, self.listA, None),\n",
    "            case(self.listA, self.listC, None),\n",
    "            case(self.listB, self.listC, None),\n",
    "            # Overlap.\n",
    "            case(self.listA, self.listCUA, [1,2,3]),\n",
    "            case(self.listCUA, self.listA, [1,2,3]),\n",
    "        ]\n",
    "        for c in cases:\n",
    "            rcv = list_overlap(c.a, c.b)\n",
    "            rcv = rcv if rcv is None else make_list(rcv)\n",
    "            self.assertEqual(rcv, c.expected)\n",
    "\n",
    "\n",
    "unittest.main(ListOverlapTest(), argv=[''], verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}