Assignment_Linked_List_Practice_Question.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5aaa1ec0-6fc2-408f-804f-587f2de783dd",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c0338005-1d2f-4a6a-9aaa-34a4f54e3932",
   "metadata": {},
   "outputs": [],
   "source": [
    "                                                  **** Assignment Questions ****"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28f9660c-8b12-4292-bcc9-88ef7ce82f41",
   "metadata": {},
   "outputs": [],
   "source": [
    "                                                  **** DSA Practice Questions ****"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3875d1f-c30b-492d-8601-5ff0e600ac39",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "db7778f4-160b-47b1-bca4-b1f9bfbe6047",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "ab15587e-f43c-4f7f-8fbd-cd9ccd87fa95",
   "metadata": {},
   "source": [
    "### 1. Define a double linked list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3a41f62-212d-4ffd-b7df-eaa4ac4990ff",
   "metadata": {},
   "source": [
    "A doubly linked list is a type of data structure that consists of a sequence of elements, each called a node. \n",
    "\n",
    "In a doubly linked list, each node contains three fields:\n",
    "1. Data: This field stores the value or information contained in the node.\n",
    "2. Next: This field is a reference (or pointer) to the next node in the sequence.\n",
    "3. Previous: This field is a reference (or pointer) to the previous node in the sequence.\n",
    "\n",
    "The key feature of a doubly linked list is that it allows traversal in both directions: forward and backward. This is achieved \n",
    "through the \"next\" and \"previous\" pointers in each node. \n",
    "\n",
    "Below is a Python implementation of a doubly linked list with basic functionalities including appending, printing, and reversing the list.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4ed06733-90db-4f9e-9534-05effd5b1430",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Forward traversal : 1 <-> 2 <-> 3 <-> 4 <-> 5 -> None\n",
      "Backward traversal : 5 <-> 4 <-> 3 <-> 2 <-> 1 -> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data, next=None, prev=None):\n",
    "        self.__data = data\n",
    "        self.__prev = prev\n",
    "        self.__next = next\n",
    "\n",
    "    def getData(self):\n",
    "        return self.__data\n",
    "\n",
    "    def setData(self, data):\n",
    "        self.__data = data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.__next\n",
    "\n",
    "    def setNext(self, next):\n",
    "        self.__next = next\n",
    "\n",
    "    def getPrev(self):\n",
    "        return self.__prev\n",
    "\n",
    "    def setPrev(self, prev):\n",
    "        self.__prev = prev\n",
    "\n",
    "# Creating nodes and linking them\n",
    "head = Node(1)\n",
    "node1 = Node(2)\n",
    "node2 = Node(3)\n",
    "node3 = Node(4)\n",
    "node4 = Node(5)\n",
    "\n",
    "head.setNext(node1)\n",
    "node1.setNext(node2)\n",
    "node1.setPrev(head)\n",
    "node2.setNext(node3)\n",
    "node2.setPrev(node1)\n",
    "node3.setNext(node4)\n",
    "node3.setPrev(node2)\n",
    "node4.setPrev(node3)\n",
    "\n",
    "# traversal function\n",
    "def traverse(head):\n",
    "    if not head:\n",
    "        return\n",
    "\n",
    "    temp = head\n",
    "\n",
    "    # Traverse forward and get to the end\n",
    "    print(\"Forward traversal : \", end=\"\")\n",
    "    while temp.getNext():\n",
    "        print(temp.getData(), end=\" <-> \")\n",
    "        temp = temp.getNext()\n",
    "    print(temp.getData(), \"-> None\")\n",
    "\n",
    "    # temp now points to the last node (tail)\n",
    "    tail = temp\n",
    "\n",
    "    # Traverse backward from the tail\n",
    "    print(\"Backward traversal : \", end=\"\")\n",
    "    while tail.getPrev():\n",
    "        print(tail.getData(), end=\" <-> \")\n",
    "        tail = tail.getPrev()\n",
    "    print(tail.getData(), \"-> None\")\n",
    "\n",
    "# Testing traversal\n",
    "traverse(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c0c803da-88f7-4027-96eb-c1f379e12a44",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "23fa6fe1-6b57-4491-84c8-969c073dfcd7",
   "metadata": {},
   "source": [
    "### 2. Write a function to reverse a linked list in-place"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ecbfcfcc-eada-4014-aa4a-b2a9d203377e",
   "metadata": {},
   "source": [
    "\n",
    "Reversing a linked list in-place involves changing the direction of the pointers of the nodes so that they point to the\n",
    "'previous' node instead of the 'next' node. Below is a Python program that defines a singly linked list and includes a \n",
    "function to reverse the linked list in-place.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3a16c0f2-338f-4d5b-ba1c-b112cd2b90b0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original List :\n",
      "Forward Traversal : 1 <-> 2 <-> 3 <-> 4 <-> 5 -> None\n",
      "Backward Traversal : 5 <-> 4 <-> 3 <-> 2 <-> 1 -> None\n",
      "\n",
      "Reversed List :\n",
      "Forward Traversal : 5 <-> 4 <-> 3 <-> 2 <-> 1 -> None\n",
      "Backward Traversal : 1 <-> 2 <-> 3 <-> 4 <-> 5 -> None\n"
     ]
    }
   ],
   "source": [
    "\n",
    "class Node:\n",
    "    def __init__(self, data, next=None, prev=None):\n",
    "        self.__data = data\n",
    "        self.__prev = prev\n",
    "        self.__next = next\n",
    "\n",
    "    def getData(self):\n",
    "        return self.__data\n",
    "\n",
    "    def setData(self, data):\n",
    "        self.__data = data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.__next\n",
    "\n",
    "    def setNext(self, next):\n",
    "        self.__next = next\n",
    "\n",
    "    def getPrev(self):\n",
    "        return self.__prev\n",
    "\n",
    "    def setPrev(self, prev):\n",
    "        self.__prev = prev\n",
    "\n",
    "# Function to reverse the doubly linked list in-place\n",
    "def reverse(head):\n",
    "    if not head:\n",
    "        return None\n",
    "\n",
    "    current = head\n",
    "    prev_node = None\n",
    "\n",
    "    while current:\n",
    "        # Swap next and prev pointers\n",
    "        next_node = current.getNext()\n",
    "        current.setNext(current.getPrev())\n",
    "        current.setPrev(next_node)\n",
    "\n",
    "        # Move to the next node in the original list\n",
    "        prev_node = current\n",
    "        current = next_node\n",
    "\n",
    "    # After the loop, prev_node will be the new head\n",
    "    return prev_node\n",
    "\n",
    "# Helper function to create a list and traverse it\n",
    "def create_and_traverse():\n",
    "    head = Node(1)\n",
    "    node1 = Node(2)\n",
    "    node2 = Node(3)\n",
    "    node3 = Node(4)\n",
    "    node4 = Node(5)\n",
    "\n",
    "    head.setNext(node1)\n",
    "    node1.setNext(node2)\n",
    "    node1.setPrev(head)\n",
    "    node2.setNext(node3)\n",
    "    node2.setPrev(node1)\n",
    "    node3.setNext(node4)\n",
    "    node3.setPrev(node2)\n",
    "    node4.setPrev(node3)\n",
    "\n",
    "    print(\"Original List :\")\n",
    "    traverse(head)\n",
    "\n",
    "    head = reverse(head)\n",
    "\n",
    "    print(\"\\nReversed List :\")\n",
    "    traverse(head)\n",
    "\n",
    "\n",
    "def traverse(head):\n",
    "    if not head:\n",
    "        return\n",
    "\n",
    "    temp = head\n",
    "\n",
    "    # Traverse forward and get to the end\n",
    "    print(\"Forward Traversal : \", end=\"\")\n",
    "    while temp.getNext():\n",
    "        print(temp.getData(), end=\" <-> \")\n",
    "        temp = temp.getNext()\n",
    "    print(temp.getData(), \"-> None\")\n",
    "\n",
    "    # temp now points to the last node (tail)\n",
    "    tail = temp\n",
    "\n",
    "    # Traverse backward from the tail\n",
    "    print(\"Backward Traversal : \", end=\"\")\n",
    "    while tail.getPrev():\n",
    "        print(tail.getData(), end=\" <-> \")\n",
    "        tail = tail.getPrev()\n",
    "    print(tail.getData(), \"-> None\")\n",
    "\n",
    "# Testing the reversal\n",
    "create_and_traverse()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "657c1d6f-2abd-4cd7-a931-4240578f3cf8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "bb560970-a59a-40f7-8b9c-501e335b3839",
   "metadata": {},
   "source": [
    "### 3. Detect cycle in a linked list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e385593a-ca1e-498d-ae94-767154fb73d3",
   "metadata": {},
   "source": [
    "Detecting a cycle in a linked list can be efficiently achieved using 'Floyd’s Tortoise and Hare algorithm'. This algorithm uses\n",
    "two pointers that move at different speeds. If there's a cycle, these pointers will eventually meet.\n",
    "\n",
    "Simple Explanation:\n",
    "1. Tortoise and Hare Pointers:\n",
    "   - Start both pointers at the head of the list.\n",
    "   - Move the \"tortoise\" pointer one step at a time.\n",
    "   - Move the \"hare\" pointer two steps at a time.\n",
    "\n",
    "2. Cycle Detection:\n",
    "   - If the linked list has a cycle, the fast-moving hare will eventually meet the slow-moving tortoise within the cycle.\n",
    "   - If the hare reaches the end of the list (i.e., a None value), the list does not have a cycle.\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "b8bc0fa9-24d6-4428-85d0-d366621bf7a4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cycle in linked list : False\n",
      "Cycle in linked list : True\n"
     ]
    }
   ],
   "source": [
    "\n",
    "class ListNode:\n",
    "    def __init__(self, value=0, next=None):\n",
    "        self.value = value\n",
    "        self.next = next\n",
    "\n",
    "def has_cycle(head):\n",
    "    if not head:\n",
    "        return False\n",
    "\n",
    "    tortoise = head\n",
    "    hare = head\n",
    "\n",
    "    while hare and hare.next:\n",
    "        tortoise = tortoise.next\n",
    "        hare = hare.next.next\n",
    "\n",
    "        if tortoise == hare:\n",
    "            return True\n",
    "\n",
    "    return False\n",
    "\n",
    "# Example usage:\n",
    "if __name__ == \"__main__\":\n",
    "    # Create a cycle-free linked list: 1 -> 2 -> 3 -> 4 -> 5 -> None\n",
    "    head = ListNode(1)\n",
    "    head.next = ListNode(2)\n",
    "    head.next.next = ListNode(3)\n",
    "    head.next.next.next = ListNode(4)\n",
    "    head.next.next.next.next = ListNode(5)\n",
    "\n",
    "    print(\"Cycle in linked list :\", has_cycle(head))  # Output: False\n",
    "\n",
    "    # Create a cycle: 1 -> 2 -> 3 -> 4 -> 5 -> 3 ...\n",
    "    head.next.next.next.next.next = head.next.next\n",
    "\n",
    "    print(\"Cycle in linked list :\", has_cycle(head))  # Output: True\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "67ce0abb-774f-431c-86a2-725d2fcd2a18",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "### Explanation of the Code:\n",
    "\n",
    "1. ListNode Class:\n",
    "   - Defines the structure of a node in the linked list, with a value and a pointer to the next node.\n",
    "\n",
    "2. has_cycle Function:\n",
    "   - Takes the head of the linked list as input.\n",
    "   - Initializes two pointers, tortoise and hare, to the head.\n",
    "   - Uses a while loop to move the tortoise one step and the hare two steps until either a cycle is detected \n",
    "     (tortoise meets hare) or the hare reaches the end of the list (no cycle).\n",
    "\n",
    "3. Example Usage:\n",
    "   - Demonstrates the function with both a cycle-free list and a list with a cycle.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67fd6099-7905-4134-8e73-a61ed3a7baba",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "6c066e2e-bb14-459c-9f11-3b2a3daf9c9b",
   "metadata": {},
   "source": [
    "### 4. Merge two sorted linked list into one"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1a8d8137-186a-4636-af4d-565df387c008",
   "metadata": {},
   "source": [
    "### 1->3->5->6->null and 2->4->6->8->null should be merged to make\n",
    "\n",
    "### 1->2->3->4->5->6->7->8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c224a45a-7290-405f-8321-9e5287c6ec3c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List 1 :\n",
      "1 -> 3 -> 5 -> 6 -> None\n",
      "List 2 :\n",
      "2 -> 4 -> 6 -> 8 -> None\n",
      "\n",
      "Merged List of two sorted linked list into one :\n",
      "1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 6 -> 8 -> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data, next=None):\n",
    "        self.__data = data\n",
    "        self.__next = next\n",
    "\n",
    "    def getData(self):\n",
    "        return self.__data\n",
    "\n",
    "    def setData(self, data):\n",
    "        self.__data = data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.__next\n",
    "\n",
    "    def setNext(self, next):\n",
    "        self.__next = next\n",
    "\n",
    "# Function to merge two sorted linked lists\n",
    "def merge_sorted_lists(head1, head2):\n",
    "    # Create a dummy node to simplify the merging process\n",
    "    dummy = Node(0)\n",
    "    tail = dummy\n",
    "\n",
    "    # Traverse both lists and merge them\n",
    "    while head1 and head2:\n",
    "        if head1.getData() < head2.getData():\n",
    "            tail.setNext(head1)\n",
    "            head1 = head1.getNext()\n",
    "        else:\n",
    "            tail.setNext(head2)\n",
    "            head2 = head2.getNext()\n",
    "        tail = tail.getNext()\n",
    "\n",
    "    # Attach the remaining nodes, if any\n",
    "    if head1:\n",
    "        tail.setNext(head1)\n",
    "    if head2:\n",
    "        tail.setNext(head2)\n",
    "\n",
    "    # The head of the merged list is the next node after the dummy node\n",
    "    return dummy.getNext()\n",
    "\n",
    "# Helper function to print the linked list\n",
    "def print_list(head):\n",
    "    temp = head\n",
    "    while temp:\n",
    "        print(temp.getData(), end=\" -> \")\n",
    "        temp = temp.getNext()\n",
    "    print(\"None\")\n",
    "\n",
    "# Helper function to create a list from an array\n",
    "def create_list(arr):\n",
    "    if not arr:\n",
    "        return None\n",
    "    head = Node(arr[0])\n",
    "    current = head\n",
    "    for value in arr[1:]:\n",
    "        current.setNext(Node(value))\n",
    "        current = current.getNext()\n",
    "    return head\n",
    "\n",
    "# Testing the merge function\n",
    "list1 = create_list([1, 3, 5, 6])\n",
    "list2 = create_list([2, 4, 6, 8])\n",
    "\n",
    "print(\"List 1 :\")\n",
    "print_list(list1)\n",
    "print(\"List 2 :\")\n",
    "print_list(list2)\n",
    "\n",
    "merged_list = merge_sorted_lists(list1, list2)\n",
    "print(\"\\nMerged List of two sorted linked list into one :\")\n",
    "print_list(merged_list)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6f5603d8-72d2-42ac-ba8d-00ad0c5a28f1",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7c162503-9695-4a16-83a7-e243598c6f9a",
   "metadata": {},
   "source": [
    "### 5. Write a function to remove nth code from the end in a linked list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "56f641bf-e9f1-4a12-9cb4-60e6cac293f9",
   "metadata": {},
   "source": [
    "### 1->2->3->4->5->6, removing 2nd node from end will return 1->2->3->4->6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "652bff69-cafd-4200-ba58-6a96e10281f4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original list :\n",
      "1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None\n",
      "\n",
      "List after removing 2-th node from end :\n",
      "1 -> 2 -> 3 -> 4 -> 6 -> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data, next=None):\n",
    "        self.__data = data\n",
    "        self.__next = next\n",
    "\n",
    "    def getData(self):\n",
    "        return self.__data\n",
    "\n",
    "    def setData(self, data):\n",
    "        self.__data = data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.__next\n",
    "\n",
    "    def setNext(self, next):\n",
    "        self.__next = next\n",
    "\n",
    "# Function to remove the n-th node from the end of the list\n",
    "def remove_nth_from_end(head, n):\n",
    "    # Create a dummy node to simplify edge cases\n",
    "    dummy = Node(0)\n",
    "    dummy.setNext(head)\n",
    "    \n",
    "    first = dummy\n",
    "    second = dummy\n",
    "    \n",
    "    # Move first pointer n+1 steps ahead\n",
    "    for _ in range(n + 1):\n",
    "        first = first.getNext()\n",
    "\n",
    "    # Move both pointers until first reaches the end\n",
    "    while first:\n",
    "        first = first.getNext()\n",
    "        second = second.getNext()\n",
    "\n",
    "    # Remove the n-th node from the end\n",
    "    second.setNext(second.getNext().getNext())\n",
    "    \n",
    "    return dummy.getNext()\n",
    "\n",
    "# Helper function to print the linked list\n",
    "def print_list(head):\n",
    "    temp = head\n",
    "    while temp:\n",
    "        print(temp.getData(), end=\" -> \")\n",
    "        temp = temp.getNext()\n",
    "    print(\"None\")\n",
    "\n",
    "# Helper function to create a list from an array\n",
    "def create_list(arr):\n",
    "    if not arr:\n",
    "        return None\n",
    "    head = Node(arr[0])\n",
    "    current = head\n",
    "    for value in arr[1:]:\n",
    "        current.setNext(Node(value))\n",
    "        current = current.getNext()\n",
    "    return head\n",
    "\n",
    "# Testing the function\n",
    "head = create_list([1, 2, 3, 4, 5, 6])\n",
    "\n",
    "print(\"Original list :\")\n",
    "print_list(head)\n",
    "\n",
    "n = 2\n",
    "head = remove_nth_from_end(head, n)\n",
    "\n",
    "print(f\"\\nList after removing {n}-th node from end :\")\n",
    "print_list(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c97091d1-d855-4835-add8-f14997c01323",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "39d86842-cf2d-4486-8007-22d5e297cd3e",
   "metadata": {},
   "source": [
    "### 6. Remove duplicates from a sorted linked list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ffeeb7d2-cb9d-465f-88fc-398b3da7410d",
   "metadata": {},
   "source": [
    "### 1->2->3->3->4->4->4->5  should be changed to 1->2->3->4->5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "719b6db1-571d-4bce-8044-403f83d6ed07",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original list :\n",
      "1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 4 -> 5 -> None\n",
      "\n",
      "List after removing duplicates :\n",
      "1 -> 2 -> 3 -> 4 -> 5 -> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data, next=None):\n",
    "        self.__data = data\n",
    "        self.__next = next\n",
    "\n",
    "    def getData(self):\n",
    "        return self.__data\n",
    "\n",
    "    def setData(self, data):\n",
    "        self.__data = data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.__next\n",
    "\n",
    "    def setNext(self, next):\n",
    "        self.__next = next\n",
    "\n",
    "# Function to remove duplicates from a sorted linked list\n",
    "def remove_duplicates(head):\n",
    "    current = head\n",
    "\n",
    "    while current and current.getNext():\n",
    "        if current.getData() == current.getNext().getData():\n",
    "            current.setNext(current.getNext().getNext())\n",
    "        else:\n",
    "            current = current.getNext()\n",
    "\n",
    "    return head\n",
    "\n",
    "# Helper function to print the linked list\n",
    "def print_list(head):\n",
    "    temp = head\n",
    "    while temp:\n",
    "        print(temp.getData(), end=\" -> \")\n",
    "        temp = temp.getNext()\n",
    "    print(\"None\")\n",
    "\n",
    "# Helper function to create a list from an array\n",
    "def create_list(arr):\n",
    "    if not arr:\n",
    "        return None\n",
    "    head = Node(arr[0])\n",
    "    current = head\n",
    "    for value in arr[1:]:\n",
    "        current.setNext(Node(value))\n",
    "        current = current.getNext()\n",
    "    return head\n",
    "\n",
    "# Testing the function\n",
    "head = create_list([1, 2, 3, 3, 4, 4, 4, 5])\n",
    "\n",
    "print(\"Original list :\")\n",
    "print_list(head)\n",
    "\n",
    "head = remove_duplicates(head)\n",
    "\n",
    "print(\"\\nList after removing duplicates :\")\n",
    "print_list(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c14c1c5f-5a28-4d73-bb12-165b46915dbd",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "2da73bb6-38f0-45be-abc7-0513cb8f9bd2",
   "metadata": {},
   "source": [
    "### 7. Find the intersection of the two linked lists"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "11857856-190e-4f12-b537-fcac54eb8afc",
   "metadata": {},
   "source": [
    "### 1->2->3->4->8->6->9  5->1->6->7  , intersection 1->6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "f6a6105b-bc62-477b-ba56-0aeb66134d05",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List 1 :\n",
      "1 -> 2 -> 3 -> 4 -> 6 -> 9 -> None\n",
      "List 2 :\n",
      "5 -> 1 -> 6 -> 9 -> None\n",
      "\n",
      "Intersection at node with data : 6\n"
     ]
    }
   ],
   "source": [
    "\n",
    "class Node:\n",
    "    def __init__(self, data, next=None):\n",
    "        self.__data = data\n",
    "        self.__next = next\n",
    "\n",
    "    def getData(self):\n",
    "        return self.__data\n",
    "\n",
    "    def setData(self, data):\n",
    "        self.__data = data\n",
    "\n",
    "    def getNext(self):\n",
    "        return self.__next\n",
    "\n",
    "    def setNext(self, next):\n",
    "        self.__next = next\n",
    "\n",
    "# Function to find the length of a linked list\n",
    "def get_length(head):\n",
    "    length = 0\n",
    "    current = head\n",
    "    while current:\n",
    "        length += 1\n",
    "        current = current.getNext()\n",
    "    return length\n",
    "\n",
    "# Function to find the intersection of two linked lists\n",
    "def find_intersection(head1, head2):\n",
    "    length1 = get_length(head1)\n",
    "    length2 = get_length(head2)\n",
    "\n",
    "    # Advance the pointer of the longer list by the difference in lengths\n",
    "    if length1 > length2:\n",
    "        for _ in range(length1 - length2):\n",
    "            head1 = head1.getNext()\n",
    "    else:\n",
    "        for _ in range(length2 - length1):\n",
    "            head2 = head2.getNext()\n",
    "\n",
    "    # Traverse both lists simultaneously to find the intersection\n",
    "    while head1 and head2:\n",
    "        if head1.getData() == head2.getData():\n",
    "            return head1  # Intersection found\n",
    "        head1 = head1.getNext()\n",
    "        head2 = head2.getNext()\n",
    "\n",
    "    return None  # No intersection\n",
    "\n",
    "# Helper function to print the linked list\n",
    "def print_list(head):\n",
    "    temp = head\n",
    "    while temp:\n",
    "        print(temp.getData(), end=\" -> \")\n",
    "        temp = temp.getNext()\n",
    "    print(\"None\")\n",
    "\n",
    "# Helper function to create a list from an array\n",
    "def create_list(arr):\n",
    "    if not arr:\n",
    "        return None\n",
    "    head = Node(arr[0])\n",
    "    current = head\n",
    "    for value in arr[1:]:\n",
    "        current.setNext(Node(value))\n",
    "        current = current.getNext()\n",
    "    return head\n",
    "\n",
    "# Testing the function\n",
    "# Create two linked lists with an intersection\n",
    "head1 = create_list([1, 2, 3, 4, 8, 6, 9])\n",
    "head2 = create_list([5, 1, 6, 7])\n",
    "\n",
    "# Creating an intersection manually\n",
    "# 4th node of the first list intersects with the 2nd node of the second list\n",
    "intersecting_node = Node(6)\n",
    "head1.getNext().getNext().getNext().setNext(intersecting_node)\n",
    "head2.getNext().setNext(intersecting_node)\n",
    "intersecting_node.setNext(Node(9))\n",
    "\n",
    "print(\"List 1 :\")\n",
    "print_list(head1)\n",
    "\n",
    "print(\"List 2 :\")\n",
    "print_list(head2)\n",
    "\n",
    "intersection = find_intersection(head1, head2)\n",
    "\n",
    "if intersection:\n",
    "    print(\"\\nIntersection at node with data :\", intersection.getData())\n",
    "else:\n",
    "    print(\"No intersection found\")\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9a1d26a0-0135-453e-a2c1-88857b30efd6",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "e187ca23-54fb-45ee-8eda-caf76a98700f",
   "metadata": {},
   "source": [
    "### 8. Rotate a linked list by k positions to the right"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "668a420a-6161-4508-8cac-b157564d75f1",
   "metadata": {},
   "source": [
    "### 1->2->3->4->8->6->9 , after rotating for 2 times becomes , 3->4->8->6->9->1->2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b747515e-22cb-4044-a52b-c63d69a886f9",
   "metadata": {},
   "source": [
    "\n",
    "## Rotating a linked list by 𝑘 positions to the right means shifting each node k positions forward in the list. \n",
    "Nodes that move past the end of the list wrap around to the beginning. \n",
    "\n",
    "Let's go through the steps with a simple example.\n",
    "\n",
    "### Example\n",
    "Given linked list:\n",
    "\n",
    "1 -> 2 -> 3 -> 4 -> 8 -> 6 -> 9\n",
    "\n",
    "## After rotating 2 times to the right, the list becomes:\n",
    "\n",
    "3 -> 4 -> 8 -> 6 -> 9 -> 1 -> 2\n",
    "\n",
    "## Steps to Rotate the List\n",
    "1. Determine the Length of the List:\n",
    "   - Traverse the list to find its length N.\n",
    "\n",
    "2. Normalize 𝑘:\n",
    "   - If 𝑘 is greater than N, compute 𝑘%𝑁 to handle rotations greater than the list's length.\n",
    "\n",
    "3. Find the New Tail and New Head:\n",
    "   - Compute the position of the new tail, which is at index (N−k−1).\n",
    "   - The new head is the node right after the new tail.\n",
    "\n",
    "4. Rearrange the Pointers:\n",
    "   - Set the next of the current tail to the current head.\n",
    "   - Set the next of the new tail to None.\n",
    "   - The new head is the start of the rotated list.\n",
    "\n",
    "### Detailed Example\n",
    "For the list 1 -> 2 -> 3 -> 4 -> 8 -> 6 -> 9 and k=2:\n",
    "\n",
    "1. Determine Length N:\n",
    "   - The length of the list N is 7.\n",
    "\n",
    "2. Normalize k:\n",
    "   - Since k=2 and k<N, no change needed.\n",
    "\n",
    "3. Find New Tail and New Head:\n",
    "   - New tail position: N−k−1=7−2−1=4. So, the new tail is 8.\n",
    "   - New head is the node after 8, which is 6.\n",
    "\n",
    "4. Rearrange the Pointers:\n",
    "   - Current tail (9) now points to the current head (1).\n",
    "   - New tail (8) points to None.\n",
    "\n",
    "\n",
    "### Resulting list:\n",
    "3 -> 4 -> 8 -> 6 -> 9 -> 1 -> 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "e8e6495d-88b4-4a93-90fc-b8d1a542bcc5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result list after rotating by 2 positions:\n",
      "6 -> 9 -> 1 -> 2 -> 3 -> 4 -> 8 -> None\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "Here's how we can implement this in Python:\n",
    "'''\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "def rotate_right(head, k):\n",
    "    if not head or not head.next or k == 0:\n",
    "        return head\n",
    "\n",
    "    # Step 1: Determine the length of the list\n",
    "    current = head\n",
    "    length = 1\n",
    "    while current.next:\n",
    "        current = current.next\n",
    "        length += 1\n",
    "\n",
    "    # Step 2: Normalize k\n",
    "    k = k % length\n",
    "    if k == 0:\n",
    "        return head\n",
    "\n",
    "    # Step 3: Find the new tail and new head\n",
    "    new_tail_pos = length - k - 1\n",
    "    new_tail = head\n",
    "    for _ in range(new_tail_pos):\n",
    "        new_tail = new_tail.next\n",
    "\n",
    "    new_head = new_tail.next\n",
    "\n",
    "    # Step 4: Rearrange the pointers\n",
    "    current.next = head  # Connect the end of the list to the head\n",
    "    new_tail.next = None  # Break the link to form the new tail\n",
    "\n",
    "    return new_head\n",
    "\n",
    "# Utility function to print the list for debugging\n",
    "def print_list(node):\n",
    "    while node:\n",
    "        print(node.val, end=\" -> \")\n",
    "        node = node.next\n",
    "    print(\"None\")\n",
    "\n",
    "# Example usage:\n",
    "# Creating test linked list 1 -> 2 -> 3 -> 4 -> 8 -> 6 -> 9\n",
    "head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(8, ListNode(6, ListNode(9)))))))\n",
    "\n",
    "# Rotating the list by 2 positions\n",
    "result = rotate_right(head, 2)\n",
    "\n",
    "# Printing the result list\n",
    "print(\"Result list after rotating by 2 positions:\")\n",
    "print_list(result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7162e2be-ca8f-43f9-885a-e1af5154d6dc",
   "metadata": {},
   "source": [
    "### Explanation of the Code:\n",
    "    \n",
    "1. ListNode Class:\n",
    "   - Represents each node in the linked list with val (value) and next (pointer to the next node).\n",
    "\n",
    "2. rotate_right Function:\n",
    "   - Computes the length of the list and normalizes k to handle large k values.\n",
    "   - Identifies the new tail and new head based on the rotation.\n",
    "   - Rearranges the pointers to form the rotated list.\n",
    "\n",
    "3. print_list Function:\n",
    "   - A utility function to print the linked list for verification.\n",
    "\n",
    "### This method efficiently rotates the linked list by k positions to the right in 𝑂(𝑁)time.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed3e9e52-4704-49e4-8579-99fa706310cf",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "7b502f52-7b1f-423a-ab59-e4852379ff5b",
   "metadata": {},
   "source": [
    "### 9. Add Two Numbers Represented by LinkedLists:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "998675b7-bfa8-4d3b-9273-26df1cded2d5",
   "metadata": {},
   "source": [
    "### Given two non-empty linked lists representing two non-negative integers, where the digits are stored in reverse order, add the two numbers and return it as a linked list."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6186b361-cc8c-4c3b-a3ae-7cf459a70091",
   "metadata": {},
   "source": [
    "\n",
    "To add two numbers represented by linked lists where each node contains a single digit and the digits are stored in \n",
    "reverse order, follow these steps:\n",
    "\n",
    "Steps to Add Two Numbers\n",
    "\n",
    "1. Initialize Pointers and Variables:\n",
    "   - Use pointers to traverse each linked list.\n",
    "   - Initialize a variable to keep track of the carry.\n",
    "\n",
    "2. Iterate through Both Lists:\n",
    "   - At each step, add the values of the nodes from both lists along with the carry.\n",
    "   - Compute the new digit and the new carry.\n",
    "   - Create a new node with the new digit and append it to the result list.\n",
    "\n",
    "3. Handle the Final Carry:\n",
    "   - If there is a carry left after the last addition, create a new node with this carry.\n",
    "\n",
    "Example:\n",
    "Let's take two numbers: 342 and 465. These numbers are represented as linked lists in reverse order:\n",
    "\n",
    "342: 2 -> 4 -> 3\n",
    "\n",
    "465: 5 -> 6 -> 4\n",
    "\n",
    "The expected result after adding these numbers is 807, which is represented as 7 -> 0 -> 8.\n",
    "\n",
    "\n",
    "Step-by-Step Process\n",
    "1. Initialization:\n",
    "   - Start with the head of both lists.\n",
    "   - Initialize carry to 0.\n",
    "\n",
    "2. Iterate and Add:\n",
    "   - Add 2 (from list 1) + 5 (from list 2) + 0 (carry) = 7.\n",
    "      - New digit: 7, New carry: 0.\n",
    "   - Move to the next nodes.\n",
    "   - Add 4 (from list 1) + 6 (from list 2) + 0 (carry) = 10.\n",
    "     - New digit: 0, New carry: 1.\n",
    "   - Move to the next nodes.\n",
    "   - Add 3 (from list 1) + 4 (from list 2) + 1 (carry) = 8.\n",
    "     - New digit: 8, New carry: 0.\n",
    " \n",
    "3. Handle Final Carry:\n",
    "   - There is no carry left, so we are done.\n",
    "   \n",
    "   \n",
    "Resulting Linked List:\n",
    "The result linked list will be: 7 -> 0 -> 8.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "8d23536c-60d8-4cd9-9f89-e2adcad605ed",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List 1 :\n",
      "2 -> 4 -> 3 -> None\n",
      "List 2 :\n",
      "5 -> 6 -> 4 -> None\n",
      "\n",
      "Result list:\n",
      "7 -> 0 -> 8 -> None\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "Here's how we can implement this in Python:\n",
    "'''\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "def add_two_numbers(l1, l2):\n",
    "    dummy_head = ListNode(0)\n",
    "    current = dummy_head\n",
    "    carry = 0\n",
    "    \n",
    "    while l1 or l2:\n",
    "        x = l1.val if l1 else 0\n",
    "        y = l2.val if l2 else 0\n",
    "        \n",
    "        total = carry + x + y\n",
    "        carry = total // 10\n",
    "        current.next = ListNode(total % 10)\n",
    "        current = current.next\n",
    "        \n",
    "        if l1:\n",
    "            l1 = l1.next\n",
    "        if l2:\n",
    "            l2 = l2.next\n",
    "    \n",
    "    if carry > 0:\n",
    "        current.next = ListNode(carry)\n",
    "    \n",
    "    return dummy_head.next\n",
    "\n",
    "# Utility function to print the list for debugging\n",
    "def print_list(node):\n",
    "    while node:\n",
    "        print(node.val, end=\" -> \")\n",
    "        node = node.next\n",
    "    print(\"None\")\n",
    "\n",
    "# Example usage:\n",
    "# Creating test linked lists\n",
    "l1 = ListNode(2, ListNode(4, ListNode(3)))\n",
    "l2 = ListNode(5, ListNode(6, ListNode(4)))\n",
    "print(\"List 1 :\")\n",
    "print_list(l1)\n",
    "print(\"List 2 :\")\n",
    "print_list(l2)\n",
    "\n",
    "# Adding the two numbers\n",
    "result = add_two_numbers(l1, l2)\n",
    "\n",
    "# Printing the result list\n",
    "print(\"\\nResult list:\")\n",
    "print_list(result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cd1a103-5f46-4515-8881-005db57db07a",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "### Explanation of the Code:\n",
    "\n",
    "1. ListNode Class:\n",
    "   - Represents each node in the linked list with val (value) and next (pointer to the next node).\n",
    "\n",
    "2. add_two_numbers Function:\n",
    "   - Initializes a dummy head to simplify the creation of the result list.\n",
    "   - Uses a loop to traverse both linked lists and add corresponding digits.\n",
    "   - Manages the carry over for sums greater than 9.\n",
    "   - Appends the final carry if any to the result list.\n",
    "\n",
    "3. print_list Function:\n",
    "   - A utility function to print the linked list for verification.\n",
    "\n",
    "By following this method, we can add two numbers represented by linked lists and obtain the result as a new linked list.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a9f0909b-3dd2-45cd-997c-7c261da0fae3",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "11d92bdd-929f-47cb-bd8f-8a9b8634e917",
   "metadata": {},
   "source": [
    "### 10. Clone a Linked List with next and Random Pointer"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8e8255d2-9869-44cc-891c-34658a547f16",
   "metadata": {},
   "source": [
    "### Given a linked list of size N where each node has two links: one pointer points to the next node and the second pointer points to any node in the list. The task is to create a clone of this linked list in O(N) time. \n",
    "\n",
    "### Note: The pointer pointing to the next node is ‘next‘ pointer and the one pointing to an arbitrary node is called ‘arbit’ pointer as it can point to any arbitrary node in the linked list"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d988df62-4327-473c-89e0-99b9135b53c3",
   "metadata": {},
   "source": [
    "\n",
    "To clone a linked list with both \"next\" and \"random\" (or \"arbitrary\") pointers in '𝑂(𝑁)'time, we can use the following approach. \n",
    "This method involves three main steps: \n",
    "creating new nodes and interweaving them with the original nodes, setting the random pointers of the new nodes, and separating\n",
    "the new list from the original list.\n",
    "\n",
    "Here's the step-by-step process with an example:\n",
    "\n",
    "1. Interweave the cloned nodes with the original nodes:\n",
    "   - Traverse the original list and create new nodes for each node in the original list. Insert each new node right after the\n",
    "     corresponding original node.\n",
    "\n",
    "2. Set the random pointers for the cloned nodes:\n",
    "   - Traverse the modified list (with interleaved original and cloned nodes) and set the random pointers for each new node.\n",
    "\n",
    "3. Separate the cloned list from the original list:\n",
    "   - Traverse the modified list again to restore the original list and extract the cloned list.\n",
    "\n",
    "## Example :\n",
    "Consider the original linked list:\n",
    "\n",
    "1 -> 2 -> 3 -> 4\n",
    "|    |    |    |\n",
    "v    v    v    v\n",
    "3    1    4    2\n",
    "Here, the numbers represent the node values, and the arrows represent the next and random pointers.\n",
    "\n",
    "### Step 1: Interweave the cloned nodes\n",
    "\n",
    "1 -> 1' -> 2 -> 2' -> 3 -> 3' -> 4 -> 4'\n",
    "|           |           |           |\n",
    "v           v           v           v\n",
    "3           1           4           2\n",
    "\n",
    "Each cloned node (denoted with a prime symbol ') is inserted immediately after its original counterpart.\n",
    "\n",
    "### Step 2: Set the random pointers for the cloned nodes\n",
    "\n",
    "1 -> 1' -> 2 -> 2' -> 3 -> 3' -> 4 -> 4'\n",
    "|    |    |    |    |    |    |    |\n",
    "v    v    v    v    v    v    v    v\n",
    "3 -> 3'   1 -> 1'   4 -> 4'   2 -> 2'\n",
    "\n",
    "The random pointers for the new nodes are set based on the random pointers of the original nodes. \n",
    "\n",
    "For instance, if the random pointer of node 1 points to node 3, the random pointer of node 1' should point to node 3'.\n",
    "\n",
    "### Step 3: Separate the cloned list from the original list\n",
    "\n",
    "Original list: 1 -> 2 -> 3 -> 4\n",
    "               |    |    |    |\n",
    "               v    v    v    v\n",
    "               3    1    4    2\n",
    "\n",
    "Cloned list: 1' -> 2' -> 3' -> 4'\n",
    "             |    |    |    |\n",
    "             v    v    v    v\n",
    "             3'   1'   4'   2'\n",
    "\n",
    "The original list is restored to its initial state, and the cloned list is separated out.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c7f5146a-4d72-4080-80d8-bebb93ad0b96",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original list:\n",
      "Node data: 1, Random data: 3\n",
      "Node data: 2, Random data: 1\n",
      "Node data: 3, Random data: 4\n",
      "Node data: 4, Random data: 2\n",
      "\n",
      "Cloned list:\n",
      "Node data: 1, Random data: 3\n",
      "Node data: 2, Random data: 1\n",
      "Node data: 3, Random data: 4\n",
      "Node data: 4, Random data: 2\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "Here's how you can implement this in Python:\n",
    "'''\n",
    "class Node:\n",
    "    def __init__(self, data, next=None, random=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\n",
    "def clone_linked_list(head):\n",
    "    if not head:\n",
    "        return None\n",
    "\n",
    "    # Step 1: Create new nodes and interleave them with the original nodes\n",
    "    current = head\n",
    "    while current:\n",
    "        new_node = Node(current.data, current.next)\n",
    "        current.next = new_node\n",
    "        current = new_node.next\n",
    "\n",
    "    # Step 2: Set the random pointers for the new nodes\n",
    "    current = head\n",
    "    while current:\n",
    "        if current.random:\n",
    "            current.next.random = current.random.next\n",
    "        current = current.next.next\n",
    "\n",
    "    # Step 3: Separate the cloned list from the original list\n",
    "    original = head\n",
    "    clone_head = head.next\n",
    "    clone_current = clone_head\n",
    "\n",
    "    while original:\n",
    "        original.next = original.next.next\n",
    "        if clone_current.next:\n",
    "            clone_current.next = clone_current.next.next\n",
    "        original = original.next\n",
    "        clone_current = clone_current.next\n",
    "\n",
    "    return clone_head\n",
    "\n",
    "# Utility function to print the list for debugging\n",
    "def print_list(head):\n",
    "    current = head\n",
    "    while current:\n",
    "        random_data = current.random.data if current.random else \"None\"\n",
    "        print(f\"Node data: {current.data}, Random data: {random_data}\")\n",
    "        current = current.next\n",
    "\n",
    "# Example usage:\n",
    "# Creating a test linked list\n",
    "node1 = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(4)\n",
    "\n",
    "node1.next = node2\n",
    "node2.next = node3\n",
    "node3.next = node4\n",
    "\n",
    "node1.random = node3\n",
    "node2.random = node1\n",
    "node3.random = node4\n",
    "node4.random = node2\n",
    "\n",
    "# Cloning the list\n",
    "cloned_head = clone_linked_list(node1)\n",
    "\n",
    "# Printing the original and cloned lists\n",
    "print(\"Original list:\")\n",
    "print_list(node1)\n",
    "print(\"\\nCloned list:\")\n",
    "print_list(cloned_head)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b34b3c25-4ecd-4cb6-8e72-cfa626ed3e19",
   "metadata": {},
   "source": [
    "\n",
    "This code snippet first defines a Node class and a function clone_linked_list that performs the cloning process. \n",
    "The utility function print_list helps to verify the correctness of the cloned list by printing each node's data and its\n",
    "random pointer's data. \n",
    "The above example usage demonstrates how to create a linked list, clone it, and print both the original and cloned lists.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "20d86a67-fd78-462e-9bfb-a5f1c4b8bee8",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "396e8b0e-a541-4a8c-8fea-d15db58eb0cd",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "752e7f02-d51d-4952-a764-cf78ee5f8a69",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9915abbe-3e50-40ec-8a2b-c26970902de0",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}