Reverse part of linked list

reverse_mn.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Partial linked list reversal\n",
    "Given *m* and *n* s.t. 1 <= *m* <= *n* <= length of linked list, reverse part of the linked list starting with *m* and ending with *n* with 1-base indexing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Preliminary steps\n",
    "How do we implement a linked list?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class ListNode:\n",
    "    \"\"\"Linked list is built of nodes.\"\"\"\n",
    "    def __init__(self, val=None):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "    def __str__(self):\n",
    "        return str(self.val) + '->' + str(self.next)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at how we initialize a linked list. Variable that references a node essentially references a list that starts with that node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->None\n"
     ]
    }
   ],
   "source": [
    "linked_list1 = ListNode(1)\n",
    "linked_list1.next = ListNode(2)\n",
    "print(linked_list1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2->None\n"
     ]
    }
   ],
   "source": [
    "linked_list2 = linked_list1.next\n",
    "print(linked_list2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We may need to create bigger lists for testing, so let's write a function to build linked lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def build_list(a):\n",
    "    \"\"\"Takes a python list and builds a linked list with the same elements.\"\"\"\n",
    "    head = current = ListNode()\n",
    "    for val in a:\n",
    "        current.next = ListNode(val)\n",
    "        current = current.next\n",
    "    return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5->None\n"
     ]
    }
   ],
   "source": [
    "linked_list3 = build_list([1,2,3,4,5])\n",
    "print(linked_list3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Reverse a linked list\n",
    "Let's review how normal reversal is done."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def reverse(head):\n",
    "    \"\"\"Takes a linked list, reverses it in place and returns new head.\"\"\"\n",
    "    prev = None\n",
    "    while head:\n",
    "        nxt = head.next\n",
    "        head.next = prev\n",
    "        prev = head\n",
    "        head = nxt\n",
    "    return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5->4->3->2->1->None\n"
     ]
    }
   ],
   "source": [
    "print(reverse(linked_list3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please note, this operation is destructive to the list passed to the function as it's done \"in place\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->None\n"
     ]
    }
   ],
   "source": [
    "print(linked_list3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Partial reverse starting with first element\n",
    "How would we modify the reverse function to only sort *k* first elements and leave others intact? Perhaps, pass *k* to the function and keep going through the list while *k* is bigger than 0?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def reverse_k0(head, k):\n",
    "    \"\"\"An attempt to only reverse k first elements.\"\"\"\n",
    "    prev = None\n",
    "    while k and head:\n",
    "        nxt = head.next\n",
    "        head.next = prev\n",
    "        prev = head\n",
    "        head = nxt\n",
    "        k -= 1\n",
    "    return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4->3->2->1->None\n"
     ]
    }
   ],
   "source": [
    "linked_list4 = build_list([1,2,3,4,5,6])\n",
    "print(reverse_k0(linked_list4, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Hmmm... 5 and 6 are lost. It is because *prev* is first initialized to None and then the reversed elements are glued to it. One way to fix this would be to find which element *prev* should be pointing at."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def reverse_k(head, k):\n",
    "    \"\"\"Another attempt to reversing k first elements.\"\"\"\n",
    "    prev = head\n",
    "    for _ in range(k):\n",
    "        prev = prev.next\n",
    "    while k and head:\n",
    "        nxt = head.next\n",
    "        head.next = prev\n",
    "        prev = head\n",
    "        head = nxt\n",
    "        k -= 1\n",
    "    return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4->3->2->1->5->6->None\n"
     ]
    }
   ],
   "source": [
    "linked_list4 = build_list([1,2,3,4,5,6])\n",
    "print(reverse_k(linked_list4, 4))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It works! Let's try some edge cases to make sure it's solid."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(reverse_k(build_list([]), 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3->2->1->None\n"
     ]
    }
   ],
   "source": [
    "print(reverse_k(build_list([1,2,3]), 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just as expected. In the problem definition, *n* is never bigger than the length of the list so we're done with edge cases."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Putting it all together"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One thing to note is when *m* is 2 or bigger we need to keep a number of elements in the beginning of linked list intact. We might be able to reduce the original problem to finding what starting part of the list will stay intact, reversing the rest using reverse_k function, and stitching it all together. One trick we'll have to use is creating a dummy node that will come handy when *m* is 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def reverse_mn(head, m, n):\n",
    "    \"\"\"Reverse elements from m to n (1-based indexing)\"\"\"\n",
    "    dummy = ListNode()\n",
    "    dummy.next = head\n",
    "    head = dummy\n",
    "    for _ in range(m-1):\n",
    "        head = head.next\n",
    "    head.next = reverse_k(head.next, n-m+1)\n",
    "    return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5->6->7->8->9->None\n"
     ]
    }
   ],
   "source": [
    "linked_list5 = build_list(range(1,10))\n",
    "print(linked_list5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->7->6->5->4->3->8->9->None\n"
     ]
    }
   ],
   "source": [
    "print(reverse_mn(linked_list5, 3, 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beautiful! Let's check some edge cases. First, we need to see what happens when *m* equals 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7->6->5->4->3->2->1->8->9->None\n"
     ]
    }
   ],
   "source": [
    "linked_list5 = build_list(range(1,10))\n",
    "print(reverse_mn(linked_list5, 1, 7))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That works fine. Let's see what happens when *n* equals length of the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9->8->7->6->5->4->3->2->1->None\n"
     ]
    }
   ],
   "source": [
    "linked_list5 = build_list(range(1,10))\n",
    "print(reverse_mn(linked_list5, 1, 9))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How about *m* equals to *n*?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5->6->7->8->9->None\n"
     ]
    }
   ],
   "source": [
    "linked_list5 = build_list(range(1,10))\n",
    "print(reverse_mn(linked_list5, 2, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Last but not least, let's run it a list with one element. Problem is not defined for empty lists so we don't have to check that."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->None\n"
     ]
    }
   ],
   "source": [
    "linked_list6 = build_list([1])\n",
    "print(reverse_mn(linked_list6, 1, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All done!"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}