Code_Craft_deep_clone.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNyHkPi9tthUPQKY3Rzut5l",
      "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/walkerjian/DailyCode/blob/main/Code_Craft_deep_clone.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Problem:\n",
        "Given the head to a singly linked list, where each node also has a “random” pointer that points to anywhere in the linked list, deep clone the list."
      ],
      "metadata": {
        "id": "bZgmFJEqpS5J"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Solution:\n",
        "To deep clone a singly linked list where each node has an additional \"random\" pointer pointing to any node in the list, we need to consider both the `next` and `random` pointers for each node. The cloned list should maintain the same structure and random connections as the original list.\n",
        "\n",
        "We can approach this problem in three phases:\n",
        "1. **Iterate through the original list and clone each node:** For each node, create a cloned node and insert it right next to the original node in the list. This way, each original node `N` will be followed by its clone `N'`.\n",
        "\n",
        "2. **Copy the random pointers:** For each original node `N`, its `random` pointer will be pointing to some node `R`. The corresponding cloned node `N'` should point to `R'`, which is the clone of `R` and is located next to `R` in the modified list.\n",
        "\n",
        "3. **Restore the original list and extract the cloned list:** Separate the intertwined list of original and cloned nodes back into two individual lists, restoring the original list and extracting the cloned list.\n",
        "\n",
        "Here's how you could implement this in Python:\n",
        "\n"
      ],
      "metadata": {
        "id": "1kuYFA_lpWXh"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Implementation:\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "xmVF6tyHpeOH"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WE7Ab0Wko4Tf",
        "outputId": "51024944-02bf-4905-ff8d-59045d72b701"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Original list:\n",
            "Value: 0, Arbit: 2\n",
            "Value: 1, Arbit: 0\n",
            "Value: 2, Arbit: 3\n",
            "Value: 3, Arbit: 1\n",
            "Value: 4, Arbit: None\n",
            "\n",
            "Cloned list:\n",
            "Value: 0, Arbit: 2\n",
            "Value: 1, Arbit: 0\n",
            "Value: 2, Arbit: 3\n",
            "Value: 3, Arbit: 1\n",
            "Value: 4, Arbit: None\n"
          ]
        }
      ],
      "source": [
        "class ListNode:\n",
        "    def __init__(self, x):\n",
        "        self.val = x\n",
        "        self.next = None\n",
        "        self.arbit = None\n",
        "\n",
        "def deep_clone(head):\n",
        "    if not head:\n",
        "        return None\n",
        "\n",
        "    # Clone each node and insert it next to its original\n",
        "    current = head\n",
        "    while current:\n",
        "        cloned = ListNode(current.val)\n",
        "        cloned.next = current.next\n",
        "        current.next = cloned\n",
        "        current = cloned.next\n",
        "\n",
        "    # Set up arbit pointers for the cloned nodes\n",
        "    current = head\n",
        "    while current:\n",
        "        if current.arbit:\n",
        "            current.next.arbit = current.arbit.next\n",
        "        current = current.next.next\n",
        "\n",
        "    # Separate the cloned list from the original\n",
        "    original = head\n",
        "    clone_head = head.next\n",
        "    while original:\n",
        "        clone = original.next\n",
        "        original.next = clone.next\n",
        "        clone.next = clone.next.next if clone.next else None\n",
        "        original = original.next\n",
        "\n",
        "    return clone_head\n",
        "\n",
        "# Test harness\n",
        "def print_list(head):\n",
        "    while head:\n",
        "        arbit_val = head.arbit.val if head.arbit else None\n",
        "        print(f\"Value: {head.val}, Arbit: {arbit_val}\")\n",
        "        head = head.next\n",
        "\n",
        "# Create a test list\n",
        "nodes = [ListNode(i) for i in range(5)]\n",
        "for i in range(4):\n",
        "    nodes[i].next = nodes[i + 1]\n",
        "\n",
        "# Setting up arbitrary pointers\n",
        "nodes[0].arbit = nodes[2]\n",
        "nodes[1].arbit = nodes[0]\n",
        "nodes[2].arbit = nodes[3]\n",
        "nodes[3].arbit = nodes[1]\n",
        "\n",
        "print(\"Original list:\")\n",
        "print_list(nodes[0])\n",
        "\n",
        "cloned_list = deep_clone(nodes[0])\n",
        "\n",
        "print(\"\\nCloned list:\")\n",
        "print_list(cloned_list)\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "This function takes the head of a singly linked list with `random` pointers and returns the head of a deep-cloned list. The space complexity of this algorithm is O(1), as it only uses a few pointers, and the time complexity is O(N), where N is the number of nodes in the list, since it processes each node a constant number of times.\n",
        "\n",
        "##'Arbit' Pointers:\n",
        "\"Arbit\" pointers, in the context of linked lists, refer to arbitrary pointers that can point to any node in the list, similar to the \"random\" pointers you described in your initial query. These arbit pointers add an extra layer of complexity to the list, as they do not follow the linear progression of the standard `next` pointers.\n",
        "\n",
        "In the context of deep cloning a list with arbit pointers, the challenge is to create a copy of the list where these arbit pointers point to the corresponding nodes in the cloned list, not the original list.\n",
        "\n",
        "The approach I previously outlined for handling `random` pointers can be directly applied to `arbit` pointers as well. The method involves three steps:\n",
        "\n",
        "1. **Creating cloned nodes next to their originals:** This helps in mapping the original nodes to their clones.\n",
        "\n",
        "2. **Copying the arbit pointers:** Since each original node's clone is placed adjacent to it, the cloned node's `arbit` pointer can be easily set by referring to the original node's `arbit` pointer.\n",
        "\n",
        "3. **Separating the two lists:** Finally, the intertwined list is split back into the original list and the cloned list.\n",
        "\n",
        "This method effectively maintains the arbit pointer structure in the cloned list, ensuring that each cloned node's `arbit` pointer refers to the correct node in the cloned list. The overall complexity remains O(N) in time and O(1) in space, as it avoids the need for extra data structures to track the mapping between original and cloned nodes."
      ],
      "metadata": {
        "id": "hL1cK-zmpkla"
      }
    }
  ]
}