Linked List Problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 206. Reverse Linked List (easy):\n",
    "* Reverse a singly linked list.\n",
    "* Example:\n",
    "    - Input: 1->2->3->4->5->NULL\n",
    "    - Output: 5->4->3->2->1->NULL\n",
    "\n",
    "***\n",
    "Solution:\n",
    "1. create 3 pointers: following, current, and previous\n",
    "    - current = head;\n",
    "    - following = head;\n",
    "    - previous = null\n",
    "2. while current !== null\n",
    "    - following = current\n",
    "    - current.next = previous\n",
    "    - previous = current;\n",
    "    - current = following\n",
    "    - essentially, following is used to keep track of current.next and previous is used for current.previous\n",
    "    - as we update current.next = previous, we can then use following to go to the next node until we reach the end of the list\n",
    "    - previous = null is used in the case for an empty linked list, in which we can just return null\n",
    "3. return previous if it asks you to return the head of the linked list since previous will be a non-null value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// iterative\n",
    "var reverseList = function(head) {\n",
    "    let following = head;\n",
    "    let current = head;\n",
    "    let previous = null;\n",
    "    \n",
    "    while(current !== null) {\n",
    "        following = current.next;\n",
    "        current.next = previous;\n",
    "        previous = current;\n",
    "        current = following;\n",
    "    }\n",
    "    return previous;\n",
    "};\n",
    "\n",
    "// recursive\n",
    "var reverseList = function(head) {\n",
    "    const traverse = (following, current, previous) => {\n",
    "        if(current == null) { return previous; }\n",
    "        following = current.next;\n",
    "        current.next = previous;\n",
    "        previous = current;\n",
    "        current = following;\n",
    "        return traverse(following, current, previous);\n",
    "    }\n",
    "    \n",
    "    return traverse(head, head, null);\n",
    "}\n",
    "\n",
    "// es6 syntax for in-place\n",
    "var reverseList = function(head) {\n",
    "    let [prev, current] = [null, head]\n",
    "    while(current) {\n",
    "        [current.next, prev, current] = [prev, current, current.next]\n",
    "    }\n",
    "    return prev\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 876. Middle of the Linked List (easy):\n",
    "* Given a non-empty, singly linked list with head node head, return a middle node of linked list.\n",
    "* If there are two middle nodes, return the second middle node.\n",
    "\n",
    "* Example 1:\n",
    "    - Input: [1,2,3,4,5]\n",
    "    - Output: Node 3 from this list (Serialization: [3,4,5])\n",
    "    - The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).\n",
    "    - Note that we returned a ListNode object ans, such that:\n",
    "        * ans.val = 3\n",
    "        * ans.next.val = 4\n",
    "        * ans.next.next.val = 5\n",
    "        * and ans.next.next.next = NULL.\n",
    "\n",
    "* Example 2:\n",
    "    - Input: [1,2,3,4,5,6]\n",
    "    - Output: Node 4 from this list (Serialization: [4,5,6])\n",
    "    - Since the list has two middle nodes with values 3 and 4, we return the second one.\n",
    " \n",
    "\n",
    "* Note: The number of nodes in the given list will be between 1 and 100."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "// use of a slow pointer and a fast pointer\n",
    "// once the fast pointer is at the end, slow pointer is at mid\n",
    "\n",
    "var middleNode = function(head) {\n",
    "    let slow = head;\n",
    "    let fast = head;\n",
    "    \n",
    "    while(fast !== null && fast.next !== null) {\n",
    "        slow = slow.next;\n",
    "        fast = fast.next.next;\n",
    "    }\n",
    "    \n",
    "    return slow;\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 83. Remove Duplicates from Sorted List\n",
    "\n",
    "* https://leetcode.com/problems/remove-duplicates-from-sorted-list/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "/**\n",
    " * Definition for singly-linked list.\n",
    " * function ListNode(val, next) {\n",
    " *     this.val = (val===undefined ? 0 : val)\n",
    " *     this.next = (next===undefined ? null : next)\n",
    " * }\n",
    " */\n",
    "/**\n",
    " * @param {ListNode} head\n",
    " * @return {ListNode}\n",
    " */\n",
    "\n",
    "var deleteDuplicates = function(head) {\n",
    "    if (head == null || head.next == null) return head;\n",
    "    \n",
    "    let prev = head;\n",
    "    let current = head.next;\n",
    "    \n",
    "    while (current !== null) {\n",
    "        if (current.val === prev.val) {\n",
    "            prev.next = current.next;\n",
    "            current = current.next;\n",
    "            continue;\n",
    "        }\n",
    "        else {\n",
    "            prev = current;\n",
    "            current = current.next;\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return head;\n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Javascript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "13.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}