{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1>206. Reverse Linked List</h1>\n",
    "<hr>\n",
    "\n",
    "<!--Copy Paste Leetcode statement between-->\n",
    "<p>Reverse a singly linked list.</p>\n",
    "\n",
    "<p><strong>Example:</strong></p>\n",
    "\n",
    "<pre><strong>Input:</strong> 1-&gt;2-&gt;3-&gt;4-&gt;5-&gt;NULL\n",
    "<strong>Output:</strong> 5-&gt;4-&gt;3-&gt;2-&gt;1-&gt;NULL\n",
    "</pre>\n",
    "<!--Copy Paste Leetcode statement between-->\n",
    "<p>&nbsp;</p>\n",
    "<a href=\"https://leetcode.com/problems/reverse-linked-list/\">Source</a> \n",
    "<hr>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary Linked List\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h4>Code</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_list(head):\n",
    "    '''Iterative approach\n",
    "    Time complexity : O(n)\n",
    "    Space complexity : O(1)\n",
    "    '''\n",
    "    previous = None\n",
    "    current = head\n",
    "    while current:               #  None <-- n0 (prev)              //  current --> n2 --> n3 --> n4\n",
    "        tmp = current.next       #  None <-- n0 (prev)              //  current --> n2 (tmp) --> n3 --> n4\n",
    "        current.next = previous  #  None <-- n0 (prev) <-- current  //              n2 (tmp) --> n3 --> n4\n",
    "        previous = current       #  None <-- n0 <-- current (prev)  //              n2 (tmp) --> n3 --> n4\n",
    "        current = tmp            #  None <-- n0 <-- n1 (prev)       //          n2 (current) --> n3 --> n4\n",
    "    return previous"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<hr>\n",
    "<h4>Follow up:</h4>\n",
    "<p>A linked list can be reversed either iteratively or recursively. Could you implement both?</p>\n",
    "\n",
    "<h4>Code</h4>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverse_list(head):\n",
    "    '''Recursive approach (a bit more subtle).\n",
    "\n",
    "    the key is to work backwards.\n",
    "    Assume that the rest of the list had already been reversed,\n",
    "    now how do I reverse the front part?\n",
    "    Let's assume the list is: n1 → ... → nk-1 → nk → nk+1 → ... → nm → Ø\n",
    "\n",
    "    Assume from node nk+1 to nm had been reversed and you are at node nk.\n",
    "    n1 → ... → nk-1 → nk → nk+1 ← ... ← nm\n",
    "    We want nk+1’s next node to point to nk.\n",
    "    So, nk.next.next = nk;\n",
    "\n",
    "    Be very careful that n1's next must point to None.\n",
    "    If you forget about this, your linked list has a cycle in it.\n",
    "    This bug could be caught if you test your code with a linked list of size 2.\n",
    "\n",
    "    Time complexity : O(n)\n",
    "    Space complexity : O(n)  The extra space comes from implicit stack space due to recursion.\n",
    "    '''\n",
    "    if head is None or head.next is None:  # head == None just in case of empty list\n",
    "        return head                        # head.next == None is the real base case (when p = head)\n",
    "\n",
    "    p = reverse_list(head.next)\n",
    "    # n0 --> _ --> nm-1  --> nm (head) --> None\n",
    "    # n0 --> _ --> nm-1  --> nm (p = head) --> None\n",
    "    # n0 --> _ --> nm-1  --> nm (p) --> None\n",
    "    # n0 --> _ --> nm-1 <--> nm (p)\n",
    "    # n0 --> _ --> nm-1 <--  nm (p)    (nm-1 --> None)\n",
    "   \n",
    "    #we end up with the following:   _ --> nk-1 -->  head  --> nk+1 <-- _ <-- nm (p)    (nk+1 --> None)\n",
    "    head.next.next = head       #    _ --> nk-1 -->  head <--> nk+1 <-- _ <-- nm (p)    (nk+1 --> nk)\n",
    "    head.next = None            #    _ --> nk-1 -->  head <--  nk+1 <-- _ <-- nm (p)    (head --> None)\n",
    "    return p"
   ]
  }
 ],
 "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}