linkedLists.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNqkvX8/4ozlv3qGkKb2sPQ",
      "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/nithinaditya/ctci-python/blob/main/linkedLists.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "QnfD4c1d4o5D"
      },
      "outputs": [],
      "source": [
        "#2.2 Return Kth to Last\n",
        "#19. Remove Nth Node From End of List\n",
        "#https://leetcode.com/problems/remove-nth-node-from-end-of-list/\n",
        "class Solution:\n",
        "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
        "        dummy = ListNode(0, head)\n",
        "        left = dummy\n",
        "        right = head\n",
        "        \n",
        "        while(n > 0 and right):\n",
        "            right = right.next\n",
        "            n -= 1\n",
        "            \n",
        "        while right:\n",
        "            left = left.next\n",
        "            right = right.next\n",
        "        \n",
        "        left.next = left.next.next\n",
        "        return dummy.next\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#2.3 Delete Middle Node\n",
        "#https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/\n",
        "class Solution:\n",
        "    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
        "        new = ListNode(0)\n",
        "        new.next = head\n",
        "        prev = new\n",
        "        slow = head\n",
        "        fast = head\n",
        "        \n",
        "        while(fast and fast.next):\n",
        "            prev = slow\n",
        "            slow = slow.next\n",
        "            fast = fast.next.next\n",
        "        \n",
        "        prev.next = slow.next\n",
        "        return new.next"
      ],
      "metadata": {
        "id": "ysHoQJ7dAVxl"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#2.4 Partition of Linked List\n",
        "#https://leetcode.com/problems/partition-list/\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",
        "class Solution:\n",
        "    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:\n",
        "        \n",
        "        h1 = l1 = ListNode(0)\n",
        "        h2 = l2 = ListNode(0)\n",
        "        while head:\n",
        "            if head.val < x:\n",
        "                l1.next = head\n",
        "                l1 = l1.next\n",
        "            else:\n",
        "                l2.next = head\n",
        "                l2 = l2.next\n",
        "            head = head.next\n",
        "        l2.next = None\n",
        "        l1.next = h2.next\n",
        "        return h1.next\n",
        "        "
      ],
      "metadata": {
        "id": "k-mIGs2wA7XU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#2.6 Palindrome\n",
        "#https://leetcode.com/problems/palindrome-linked-list/\n",
        "class Solution:\n",
        "    def isPalindrome(self, head: Optional[ListNode]) -> bool:\n",
        "        new = []\n",
        "        while head:\n",
        "            new.append(head.val)\n",
        "            head = head.next\n",
        "\n",
        "        return new == new[::-1]"
      ],
      "metadata": {
        "id": "kpyrRUXH4_Ok"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#2.7 Intersection\n",
        "#https://leetcode.com/problems/intersection-of-two-linked-lists\n",
        "class Solution:\n",
        "    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:\n",
        "        l = headA\n",
        "        r = headB\n",
        "        while l != r:\n",
        "            l = l.next if l else r\n",
        "            r = r.next if r else l\n",
        "        return l\n"
      ],
      "metadata": {
        "id": "lxa3_t9O-z6-"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#2.8 Partition List\n",
        "class Solution:\n",
        "    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:\n",
        "        \n",
        "        h1 = l1 = ListNode(0)\n",
        "        h2 = l2 = ListNode(0)\n",
        "        while head:\n",
        "            if head.val < x:\n",
        "                l1.next = head\n",
        "                l1 = l1.next\n",
        "            else:\n",
        "                l2.next = head\n",
        "                l2 = l2.next\n",
        "            head = head.next\n",
        "        l2.next = None\n",
        "        l1.next = h2.next\n",
        "        return h1.next\n",
        "        "
      ],
      "metadata": {
        "id": "X3zp54L6EWF_"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#2.8 Loop Detection\n",
        "#https://leetcode.com/problems/linked-list-cycle-ii/\n",
        "class Solution:\n",
        "    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
        "        new = []\n",
        "        while(head):\n",
        "            if(head.next in new):\n",
        "                return head\n",
        "            else:\n",
        "                new.append(head.next)\n",
        "                head = head.next\n",
        "        return NULL\n",
        "            \n",
        "        "
      ],
      "metadata": {
        "id": "DrD1HAhN8aSF"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "sOB-bRxNMRn_"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}