05_Linked_Lists.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/ssuzana/Data-Structures-and-Algorithms-Notebooks/blob/main/05_Linked_Lists.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "n8yYV5G4Dv_A"
      },
      "source": [
        "A (singly) linked list is a data structure that contains a sequence of nodes such that each node contains an object and a reference to the next node in the list. The first node is referred to as the head and the last node is referred to as the tail; the tail's next field is null.\n",
        "\n",
        "There are many variants of linked lists, e.g., in a *doubly linked list*, each node has a link to its predecessor; similarly, a sentinel node or a self-loop can be used instead of null to mark the end of the list.\n",
        "\n",
        "**Arrays vs. linked lists:** An array must be stored contiguously in memory. To insert an element at a given index in an array we must shift over elements of the array. Insertion in array has `O(n)` time complexity but insertion in linked list has `O(1)` time complexity (if we insert at the currect position). "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZALfn3tJDjkj"
      },
      "source": [
        "# Each node has two entries -  a \"data\" field and a \"next\" field,\n",
        "# which points to the next node in the list\n",
        "# with the next field of the last node being null\n",
        "\n",
        "class ListNode:\n",
        "  def __init__(self, val=0, next=None):\n",
        "    self.val = val\n",
        "    self.next = next\n",
        "\n",
        "# Search\n",
        "def search_list(head: ListNode, value: int) -> ListNode:\n",
        "  # Return True if value in linked list, otherwise False\n",
        "  current_node = head\n",
        "  while current_node is not None:\n",
        "    if current_node.val == value:\n",
        "      return True\n",
        "\n",
        "    current_node = current_node.next\n",
        "  return False"
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8tNM8JsbP1UU"
      },
      "source": [
        "# Insert a new node after a specified node\n",
        "def insert_after(node: ListNode, new_node: ListNode) -> None:\n",
        "  new_node.next = node.next\n",
        "  node.next = new_node"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4c245rDYSPfI"
      },
      "source": [
        "# Delete a node after a specified node. \n",
        "# Assume node is not a tail\n",
        "\n",
        "def delete_after(node: ListNode) -> None:\n",
        "  node.next = node.next.next"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "e3uTyzk4StR5",
        "outputId": "b3fd4c9e-1a58-4b65-de3e-ff26187a5293"
      },
      "source": [
        "# node3 -> node2 -> node1\n",
        "node1 = ListNode(10) # tail\n",
        "node2 = ListNode(9,node1)\n",
        "node3 = ListNode(8, node2) #head\n",
        "print(search_list(node3,10))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "vk0jtAqFOzuO",
        "outputId": "a3433205-553f-4ecd-dd61-bfd31c414a7c"
      },
      "source": [
        "print(search_list(node3, 4))\n",
        "print(search_list(node3,9))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "False\n",
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JKX35GDeRxpd",
        "outputId": "4723e9f6-8746-44e8-877c-ccf68eb0fef4"
      },
      "source": [
        "insert_after(node3, ListNode(4))\n",
        "print(search_list(node3,4))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "PghnDeOiSxa4",
        "outputId": "bb8f2058-39f9-4318-c40e-1e0927ae7f36"
      },
      "source": [
        "delete_after(node2)\n",
        "print(search_list(node3,10))"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "False\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 206. Reverse Linked List** `Easy`\n",
        "Given the head of a singly linked list, reverse the list, and return the reversed list.\n",
        "\n",
        " ```\n",
        "Example:\n",
        "Input: head = [1,2,3,4,5]\n",
        "Output: [5,4,3,2,1]\n",
        "```"
      ],
      "metadata": {
        "id": "oUHCUyws_llS"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from typing import List\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "class ListNode:\n",
        "  def __init__(self, val=0, next=None):\n",
        "    self.val = val\n",
        "    self.next = next\n",
        "\n",
        "# iterative sol: time O(n), space O(1)\n",
        "  def reverseList(head):\n",
        "    prev = None\n",
        "    cur = head\n",
        "    while cur is not None:\n",
        "      # save next node\n",
        "      temp = cur.next\n",
        "      # reverse link\n",
        "      cur.next = prev\n",
        "      # shift pointers\n",
        "      prev = cur\n",
        "      cur = temp\n",
        "    return prev\n",
        "        "
      ],
      "metadata": {
        "id": "MXJJd7gI_99d"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# recursive solution: time O(n), space O(n)\n",
        "def reverseList(head):\n",
        "        if not head or not head.next:\n",
        "            return head\n",
        "        \n",
        "        new_head = reverseList(head.next)\n",
        "        head.next.next = head\n",
        "        head.next = None\n",
        "        return new_head"
      ],
      "metadata": {
        "id": "Pu9iAqIFryH-"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 21. Merge Two Sorted Lists** `Easy`\n",
        "\n",
        "You are given the heads of two sorted linked lists `list1` and `list2`.\n",
        "\n",
        "Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.\n",
        "\n",
        "Return the head of the merged linked list.\n",
        "\n",
        "```\n",
        "Input: list1 = [1,2,4], list2 = [1,3,4]\n",
        "Output: [1,1,2,3,4,4]\n",
        "```"
      ],
      "metadata": {
        "id": "IGGAX20RC1q5"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def mergeTwoLists(list1, list2):\n",
        "  dummy = ListNode()\n",
        "  prev = dummy\n",
        "\n",
        "  while list1 and list2:\n",
        "\n",
        "    if list1.val <= list2.val:\n",
        "      prev.next = list1\n",
        "      list1 = list1.next\n",
        "    else: \n",
        "      prev.next = list2\n",
        "      list2 = list2.next\n",
        "\n",
        "    prev = prev.next\n",
        "\n",
        "  # append remaining nodes of list1 or list2\n",
        "  prev.next = list1 or list2\n",
        "\n",
        "  return dummy.next"
      ],
      "metadata": {
        "id": "oYDDY4qIDIqC"
      },
      "execution_count": 39,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# list1 = [1,2,4], list2 = [1,3,4]\n",
        "node1 = ListNode(4)\n",
        "node2 = ListNode(2,node1)\n",
        "list1 = ListNode(1, node2)\n",
        "\n",
        "n1 = ListNode(4)\n",
        "n2 = ListNode(3,n1)\n",
        "list2 = ListNode(1, n2)\n",
        "\n",
        "answer = mergeTwoLists(list1, list2)\n",
        "cur = answer\n",
        "while cur:\n",
        "  print(cur.val, end=\" \")\n",
        "  cur = cur.next"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pw2_3xu8EvJP",
        "outputId": "a25a5d87-c31e-4e99-8515-2e384455c380"
      },
      "execution_count": 40,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 1 2 3 4 4 "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 234. Palindrome Linked List** `Easy`\n",
        "Given the `head` of a singly linked list, return `true` if it is a \n",
        "palindrome or `false` otherwise.\n",
        "\n",
        "```\n",
        "Input: head = [1,2,2,1] \n",
        "1 -> 2 -> 2 -> 1\n",
        "Output: true\n",
        "```\n",
        "\n",
        "**Idea**: Reverse the back half of the list.\n",
        "To find the middle of the linked list, we'll traverse the linked list with two pointers, one of which is moving twice as fast as the other.\n",
        "When the `fast` pointer reaches the end of the list, the `slow` pointer must be in the middle."
      ],
      "metadata": {
        "id": "Wh_zNROrwgSj"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def isPalindrome(head):\n",
        "  # find middle of node\n",
        "  slow = fast = head\n",
        "  while fast and fast.next:\n",
        "    fast = fast.next.next\n",
        "    slow = slow.next\n",
        "\n",
        "  # reverse the second half\n",
        "  prev = None\n",
        "  while slow:\n",
        "    # save the next node\n",
        "    temp = slow.next\n",
        "    # reverse link\n",
        "    slow.next = prev\n",
        "    # shift pointers \n",
        "    prev = slow\n",
        "    slow = temp\n",
        "\n",
        "  # compare the first and second half nodes\n",
        "  #  1 -> 2 -> 2 <- 1\n",
        "  # head     prev\n",
        "  while prev:\n",
        "    if prev.val != head.val:\n",
        "      return False\n",
        "    prev = prev.next\n",
        "    head = head.next\n",
        "  return True"
      ],
      "metadata": {
        "id": "mbNM0Zgrx0-u"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 2487. Remove Nodes From Linked List** `Medium`\n",
        "\n",
        "You are given the `head` of a linked list.\n",
        "\n",
        "Remove every node which has a node with a **strictly greater** value anywhere to the right side of it.\n",
        "\n",
        "Return the `head` of the modified linked list.\n",
        "\n",
        "```\n",
        "Input: head = [5,2,13,3,8]\n",
        "Output: [13,8]\n",
        "```"
      ],
      "metadata": {
        "id": "bX4QF3GHVPLA"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#     def __init__(self, val=0, next=None):\n",
        "#         self.val = val\n",
        "#         self.next = next\n",
        "\n",
        "def removeNodes(head):\n",
        "    # recursive sol: time O(n), space O(n)\n",
        "    if not head:\n",
        "        return None\n",
        "\n",
        "    head.next = removeNodes(head.next)\n",
        "\n",
        "    if head.next and head.val < head.next.val:\n",
        "        return head.next\n",
        "    return head    "
      ],
      "metadata": {
        "id": "SP77wqAwVh2V"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "The following solution uses a **monotonic stack** to filter out nodes that don't satisfy the condition in the problem. \n",
        "\n",
        "When traversing the next node from the list, we have to check whether its value is greater than for any of the previous ones. It can be done by first checking the last node, then the last before last and so on. For the last nodes to be available for comparison, we maintain a stack. The nodes that break the condition in the problem are removed. This effectively makes this stack a monotonic stack, thus, ensuring that we stop comparing nodes when the condition for the current node and top node (on the stack) is restored.\n"
      ],
      "metadata": {
        "id": "TBSpgURCWl4T"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import math\n",
        "def removeNodes(head):\n",
        "    # iterative sol: time O(n), space O(n)\n",
        "    dummy = ListNode(math.inf)\n",
        "    stack = [dummy]\n",
        "    cur = head\n",
        "    \n",
        "    while cur:\n",
        "      while cur.val > stack[-1].val:\n",
        "        stack.pop()\n",
        "      stack[-1].next = cur\n",
        "      stack.append(cur)  \n",
        "      cur = cur.next\n",
        "    return dummy.next    "
      ],
      "metadata": {
        "id": "UPTy_APyWlXs"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# head = [5,2,13,3,8]\n",
        "# 5 -> 2 -> 13 -> 3 -> 8 -> None\n",
        "node1 = ListNode(8)\n",
        "node2 = ListNode(3,node1)\n",
        "node3 = ListNode(13, node2)\n",
        "node4 = ListNode(2, node3)\n",
        "head = ListNode(5, node4)\n",
        "\n",
        "updated_head = removeNodes(head)\n",
        "cur = updated_head\n",
        "while cur:\n",
        "  print(cur.val)\n",
        "  cur = cur.next"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "h37zo6egbx3l",
        "outputId": "2b9df025-321e-4242-8e0d-f686d0dd5945"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "13\n",
            "8\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 369. Plus One Linked List** `Medium`\n",
        "\n",
        "Given a non-negative integer represented as a linked list of digits, plus one to the integer.\n",
        "\n",
        "The digits are stored such that the most significant digit is at the `head` of the list.\n",
        "\n",
        "```\n",
        "Input: head = [1,2,3]\n",
        "Output: [1,2,4]\n",
        "\n",
        "Input: head = [2,4,9,3,9]\n",
        "Output: [2,4,9,4,0]\n",
        "\n",
        "Input: head = [9,9,9]\n",
        "Output: [1,0,0,0]\n",
        "\n",
        "```\n",
        "\n"
      ],
      "metadata": {
        "id": "SWfc8lqUQvq4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        " def plusOne(head: ListNode) -> ListNode:\n",
        "\n",
        "   dummy = ListNode(0)\n",
        "   dummy.next = head\n",
        "\n",
        "   processNode(dummy)\n",
        "\n",
        "   if dummy.val != 0:\n",
        "     return dummy\n",
        "   return dummy.next\n",
        "\n",
        "def processNode(node):\n",
        "  if node:\n",
        "    node.val += processNode(node.next)\n",
        "    quotient, rem = divmod(node.val, 10)\n",
        "    node.val = rem\n",
        "    return quotient\n",
        "  return 1  "
      ],
      "metadata": {
        "id": "JkGTCrlvRaPL"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# head = [2,4,9,3,9]\n",
        "node1 = ListNode(9)\n",
        "node2 = ListNode(3,node1)\n",
        "node3 = ListNode(9, node2)\n",
        "node4 = ListNode(4, node3)\n",
        "head = ListNode(2, node4)\n",
        "\n",
        "updated_head = plusOne(head)\n",
        "cur = updated_head\n",
        "while cur:\n",
        "  print(cur.val, end=\"\")\n",
        "  cur = cur.next"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "7w7506qsTOFt",
        "outputId": "7380d893-cdba-4a6c-d061-66083c73465b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "24940"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "The idea for the following solution is to identify the **rightmost** digit which is **not equal to nine** and increase that digit by one. All the following nines should be set to zero."
      ],
      "metadata": {
        "id": "VqD2OLrcVHlC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        " def plusOne(head: ListNode) -> ListNode:\n",
        "\n",
        "   dummy = ListNode(0)\n",
        "   dummy.next = head\n",
        "   not_nine = dummy\n",
        "\n",
        "   while head:\n",
        "     if head.val != 9:\n",
        "       not_nine = head\n",
        "     head = head.next\n",
        "   \n",
        "   not_nine.val += 1\n",
        "   cur = not_nine.next\n",
        "  \n",
        "   while cur:\n",
        "     cur.val = 0\n",
        "     cur = cur.next\n",
        "  \n",
        "   if dummy.val != 0:\n",
        "     return dummy\n",
        "   return dummy.next"
      ],
      "metadata": {
        "id": "8XI8NgBSVTio"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# head = [2,4,9,3,9]\n",
        "node1 = ListNode(9)\n",
        "node2 = ListNode(3,node1)\n",
        "node3 = ListNode(9, node2)\n",
        "node4 = ListNode(4, node3)\n",
        "head = ListNode(2, node4)\n",
        "\n",
        "updated_head = plusOne(head)\n",
        "cur = updated_head\n",
        "while cur:\n",
        "  print(cur.val, end=\" \")\n",
        "  cur = cur.next"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "q--nPvg0Wbm-",
        "outputId": "b40b0e2e-e846-4f28-ccaf-cd068da9a943"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "2 4 9 4 0 "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 24. Swap Nodes in Pairs** `Medium`\n",
        "\n",
        "Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)\n",
        "\n",
        "```\n",
        "Input: head = [1,2,3,4]\n",
        "Output: [2,1,4,3]\n",
        "```"
      ],
      "metadata": {
        "id": "MzK4YSTro5IU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def swapPairs(head):\n",
        "  # recursive sol: time O(n), space O(n)\n",
        "  if not head or not head.next:\n",
        "    return head\n",
        "\n",
        "  first = head\n",
        "  second = head.next\n",
        "\n",
        "  first.next = swapPairs(second.next)\n",
        "  second.next = first\n",
        "\n",
        "  return second"
      ],
      "metadata": {
        "id": "bZasVOThpVAO"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# head = [1,2,3,4]\n",
        "node1 = ListNode(4)\n",
        "node2 = ListNode(3,node1)\n",
        "node3 = ListNode(2, node2)\n",
        "head = ListNode(1, node3)\n",
        "\n",
        "updated_head = swapPairs(head)\n",
        "cur = updated_head\n",
        "while cur:\n",
        "  print(cur.val, end=\" \")\n",
        "  cur = cur.next"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "DPzr4HV9qO_s",
        "outputId": "98fad477-947c-4671-c620-f14c311e0602"
      },
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "2 1 4 3 "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 19. Remove Nth Node From End of List** `Medium`\n",
        "\n",
        "Given the `head` of a linked list, remove the `n`th node from the end of the list and return its head.\n",
        "\n",
        "```\n",
        "Input: head = [1,2,3,4,5], n = 2\n",
        "Output: [1,2,3,5]\n",
        "```"
      ],
      "metadata": {
        "id": "DGZyxLyArdvt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "Idea: The first pointer advances the list by `n+1` steps from the beginning, while the second pointer starts from the beginning of the list. Now, both pointers are exactly separated by `n` nodes apart. We maintain this constant gap by advancing both pointers together until the first pointer arrives past the last node. The second pointer will be pointing at the `n`th node counting from the last. We relink the next pointer of the node referenced by the second pointer to point to the node's next next node."
      ],
      "metadata": {
        "id": "CJ5rwP6xtn6a"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def removeNthFromEnd(head,n):\n",
        "  # time O(n), space O(1)\n",
        "  dummy = ListNode(0, head)\n",
        "  left = dummy\n",
        "  right = dummy\n",
        "  while n+1 > 0:\n",
        "    left = left.next\n",
        "    n -= 1\n",
        "   \n",
        "  # shift pointers\n",
        "  while left:\n",
        "    left = left.next\n",
        "    right = right.next\n",
        "  # delete n-th node\n",
        "  right.next = right.next.next\n",
        "\n",
        "  return dummy.next     "
      ],
      "metadata": {
        "id": "bIO7QsN9rwPa"
      },
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# head = [1,2,3,4,5], n = 2\n",
        "node1 = ListNode(5)\n",
        "node2 = ListNode(4,node1)\n",
        "node3 = ListNode(3, node2)\n",
        "node4 = ListNode(2, node3)\n",
        "head = ListNode(1, node4)\n",
        "\n",
        "updated_head = removeNthFromEnd(head, 2)\n",
        "cur = updated_head\n",
        "while cur:\n",
        "  print(cur.val, end=\" \")\n",
        "  cur = cur.next"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Lyp65X7hsiql",
        "outputId": "e34f9673-a94b-4450-aa9b-5a65bf388cc9"
      },
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 2 3 5 "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 143. Reorder List** `Medium`\n",
        "\n",
        "You are given the head of a singly linked-list. The list can be represented as:\n",
        "\n",
        "`L0 → L1 → … → Ln - 1 → Ln`\n",
        "\n",
        "Reorder the list to be on the following form:\n",
        "\n",
        "`L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …`\n",
        "\n",
        "You may not modify the values in the list's nodes. Only nodes themselves may be changed.\n",
        "\n",
        "```\n",
        "Input: head = [1,2,3,4,5]\n",
        "Output: [1,5,2,4,3]\n",
        "```"
      ],
      "metadata": {
        "id": "ZpTCzQJHxPW3"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def reorderList(head):\n",
        "  # get to the middle of the list\n",
        "  slow, fast = head, head.next\n",
        "  while fast and fast.next:\n",
        "    slow = slow.next\n",
        "    fast = fast.next.next\n",
        "\n",
        "  second = slow.next\n",
        "  slow.next = None\n",
        "\n",
        "  # reverse the second half of list\n",
        "  prev = None\n",
        "  while second:\n",
        "    temp = second.next\n",
        "    second.next = prev\n",
        "    prev, second = second, temp\n",
        "\n",
        "  # merge the two halves\n",
        "  first, second = head, prev\n",
        "  while second:\n",
        "    temp1, temp2 = first.next, second.next\n",
        "    first.next = second\n",
        "    second.next = temp1\n",
        "    first, second = temp1, temp2    \n",
        "  return head  \n"
      ],
      "metadata": {
        "id": "KAKO4QW6yGGs"
      },
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# head = [1,2,3,4,5]\n",
        "node1 = ListNode(5)\n",
        "node2 = ListNode(4,node1)\n",
        "node3 = ListNode(3, node2)\n",
        "node4 = ListNode(2, node3)\n",
        "head = ListNode(1, node4)\n",
        "\n",
        "updated_head = reorderList(head)\n",
        "cur = updated_head\n",
        "while cur:\n",
        "  print(cur.val, end=\" \")\n",
        "  cur = cur.next"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "JwbC5tGszzZK",
        "outputId": "d9cd04e7-b66e-4e22-c778-905b55cebbae"
      },
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 5 2 4 3 "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#**Leetcode 92. Reverse Linked List II** `Medium`\n",
        "\n",
        "Given the `head` of a singly linked list and two integers `left` and `right` where `left <= right`, reverse the nodes of the list from position `left` to position `right`, and return the reversed list.\n",
        "\n",
        "```\n",
        "Input: head = [1,2,3,4,5], left = 2, right = 4\n",
        "Output: [1,4,3,2,5]\n",
        "```"
      ],
      "metadata": {
        "id": "BcdK1O60S4FF"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def reverseBetween(head, left, right):\n",
        "  # time O(n), space O(1)\n",
        "  dummy = p = ListNode(0, head)\n",
        "\n",
        "  for _ in range(1, left):\n",
        "      p = p.next\n",
        "  \n",
        "  # reverse sublist\n",
        "  # 1  ------> 2 ---------> 3 -> 4 -> 5\n",
        "  # p    sublist_head\n",
        "  sublist_head = p.next\n",
        "  \n",
        "\n",
        "  while right > left:\n",
        "      # 1  ------> 2 ---------> 3 -> 4 -> 5\n",
        "      # p    sublist_head      temp\n",
        "      temp = sublist_head.next\n",
        "    \n",
        "      # 1  ------> 2            3 -> 4 -> 5\n",
        "      # p    sublist_head      temp\n",
        "      #            2   ------------> 4\n",
        "      sublist_head.next = temp.next\n",
        "      \n",
        "      # 1  ------> 2  <------  3 -> 4 -> 5\n",
        "      # p    sublist_head      temp\n",
        "      #            2   ------------> 4\n",
        "      temp.next = p.next\n",
        "\n",
        "      # 1  --> 3 -->  2  --> 4 -> 5\n",
        "      p.next = temp\n",
        "      \n",
        "      right -= 1\n",
        "\n",
        "  return dummy.next   "
      ],
      "metadata": {
        "id": "ZzfvKDNUTcyy"
      },
      "execution_count": 55,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# head = [1,2,3,4,5], left = 2, right = 4\n",
        "node1 = ListNode(5)\n",
        "node2 = ListNode(4,node1)\n",
        "node3 = ListNode(3, node2)\n",
        "node4 = ListNode(2, node3)\n",
        "head = ListNode(1, node4)\n",
        "\n",
        "ans = reverseBetween(head, 2, 4)\n",
        "cur = ans\n",
        "while cur:\n",
        "  print(cur.val, end=\" \")\n",
        "  cur = cur.next"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "U4Y_K1sGUQX_",
        "outputId": "0025a2ea-3c9e-4c58-8010-9e9e20a4aaab"
      },
      "execution_count": 56,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "1 4 3 2 5 "
          ]
        }
      ]
    }
  ]
}