leetcode_problems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Leetcode Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following class defines a node used in linked list problems. It takes as an argument the value the node holds and a pointer to the next node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    \"\"\"Class node of a linked list\n",
    "    \"\"\"    \n",
    "    def __init__(self, value) -> None:\n",
    "        \"\"\"Constructor function of a node of a lined list\n",
    "\n",
    "        Args:\n",
    "            value (int): integer value of each node\n",
    "        \"\"\"        \n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "    def __str__(self): \n",
    "        \"\"\"Overriden str function for node representation\n",
    "\n",
    "        \"\"\"         \n",
    "        return f\"node with value: {self.value} and id {id(self)}\"\n",
    "\n",
    "class myLinkedList:\n",
    "    \"\"\"Class for a linked list \n",
    "    \"\"\"\n",
    "    def __init__(self, value) -> None:\n",
    "        new_node = Node(value)\n",
    "        self.head = new_node\n",
    "        self.tail = self.head\n",
    "  \n",
    "\n",
    "    def append(self, value):\n",
    "        \"\"\"Append a node at the end of the list\n",
    "\n",
    "        Args:\n",
    "            value (int): value of the new node\n",
    "        \"\"\"        \n",
    "        # create a new node, next -> None\n",
    "        new_node = Node(value)\n",
    "        self.tail.next = new_node\n",
    "        self.tail = new_node\n",
    "\n",
    "    def __str__(self):\n",
    "        \"\"\"Overriden str of dunder method for representing the list\n",
    "        \"\"\"  \n",
    "        head_t = self.head      \n",
    "        \n",
    "        while head_t is not None:\n",
    "                print(f\"node with value {head_t.value}, with id: {id(head_t)}\")\n",
    "                head_t = head_t.next\n",
    "        if head_t is None:\n",
    "             return \"end of list reached\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " #### 1. Linked List Problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "class ListProblems(object):\n",
    "\n",
    "    @staticmethod\n",
    "    def getIntersectionNode(headA, headB):\n",
    "        \"\"\"Function that finds the node of intersection of two lists. After the intersection\n",
    "        the two lists are merged to one (thus same tail). The fact thath the two lists have \n",
    "        the same tail will be used to solve the problem with O(1) memory complexity.\n",
    "\n",
    "\n",
    "        Args:\n",
    "            headA (myLinkedList): input list 1\n",
    "            headB (myLinkedList): input list 2\n",
    "\n",
    "        Returns:\n",
    "            Node: the intesrsection node\n",
    "        \"\"\"        \n",
    "        head_a, countA, head_b, countB = headA, 0, headB, 0\n",
    "        # find the last element of the list A, along with the length of the list\n",
    "        while head_a is not None:\n",
    "            prevA = head_a\n",
    "            head_a = head_a.next\n",
    "            countA += 1\n",
    "        # find the last element of the list B,  along with the length of the list\n",
    "        while head_b is not None:\n",
    "            prevB = head_b\n",
    "            head_b = head_b.next\n",
    "            countB += 1\n",
    "        # if the tail is the same, iterate on the bigger list to make its length equal to \n",
    "        # the small one, we do not use the tail attribute of the linked list\n",
    "        if id(prevA) == id(prevB):\n",
    "            if countA >= countB:\n",
    "                diff = countA - countB\n",
    "                count = 0\n",
    "                while count < diff:\n",
    "                    headA = headA.next\n",
    "                    count += 1\n",
    "            else:\n",
    "                diff = countB - countA\n",
    "                count = 0\n",
    "                while count < diff:\n",
    "                    headB = headB.next\n",
    "                    count += 1\n",
    "            # iterate on same length lists\n",
    "            while headA is not None and headB is not None:\n",
    "                if id(headA) == id(headB):\n",
    "                    return headA\n",
    "                else:\n",
    "                    headA, headB = headA.next, headB.next\n",
    "        else:\n",
    "             return None\n",
    "        \n",
    "    def addTwoNumbers(l1, l2):\n",
    "        \"\"\"This function adds the values in two different linked lists and saves the \n",
    "        result in a third one\n",
    "\n",
    "        Args:\n",
    "            l1 (myLinkedList): input list 1\n",
    "            l2 (myLinkedList): input list 2\n",
    "\n",
    "        Returns:\n",
    "            myLinkedList: the result of the addition of the two input linked lists\n",
    "        \"\"\"      \n",
    "        carry, result = 0, None\n",
    "        p1, p2 = l1, l2\n",
    "        \n",
    "        while p1 or p2 or carry:\n",
    "            n1 = p1.value if p1 else 0\n",
    "            n2 = p2.value if p2 else 0\n",
    "            _sum = n1 + n2 + carry\n",
    "\n",
    "            # prepare next carry\n",
    "            carry = _sum // 10\n",
    "\n",
    "            # if result variable exists, append the new value, else create the list result\n",
    "            if result:\n",
    "                result.append(value=_sum % 10)\n",
    "            else:\n",
    "                result = myLinkedList(value=_sum % 10)\n",
    "\n",
    "            if p1:\n",
    "                p1 = p1.next\n",
    "            if p2:\n",
    "                p2 = p2.next\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "node with value 1, with id: 4426925712\n",
      "node with value 2, with id: 4427254736\n",
      "node with value 8, with id: 4426928208\n",
      "node with value 4, with id: 4352540176\n",
      "node with value 3, with id: 4426937168\n",
      "end of list reached\n",
      "node with value 4, with id: 4426940368\n",
      "node with value 3, with id: 4426939280\n",
      "node with value 8, with id: 4426928208\n",
      "node with value 4, with id: 4352540176\n",
      "node with value 3, with id: 4426937168\n",
      "end of list reached\n",
      "node with value: 8 and id 4426928208\n"
     ]
    }
   ],
   "source": [
    "# 1. testcases\n",
    "# construct the 'tail' list\n",
    "list1 = myLinkedList(8)\n",
    "list1.append(4)\n",
    "list1.append(3)\n",
    "\n",
    "# construct the head lists\n",
    "listA = myLinkedList(1)\n",
    "listA.append(2)\n",
    "listA.tail.next = list1.head\n",
    "\n",
    "listB = myLinkedList(4)\n",
    "listB.append(3)\n",
    "listB.tail.next = list1.head\n",
    "print(listA)\n",
    "print(listB)\n",
    "\n",
    "\n",
    "intersection_node = ListProblems.getIntersectionNode(listA.head, listB.head)\n",
    "print(intersection_node)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "node with value 2, with id: 4568795344\n",
      "node with value 4, with id: 4569024208\n",
      "node with value 3, with id: 4569989584\n",
      "end of list reached\n",
      "node with value 5, with id: 4568803792\n",
      "node with value 6, with id: 4570275600\n",
      "node with value 4, with id: 4570051088\n",
      "end of list reached\n",
      "node with value 7, with id: 4569024656\n",
      "node with value 0, with id: 4568995664\n",
      "node with value 8, with id: 4568991312\n",
      "end of list reached\n",
      "node with value 9, with id: 4569025040\n",
      "node with value 9, with id: 4563456528\n",
      "node with value 9, with id: 4570054032\n",
      "end of list reached\n",
      "node with value 9, with id: 4569027920\n",
      "node with value 9, with id: 4569989584\n",
      "end of list reached\n",
      "node with value 8, with id: 4568803792\n",
      "node with value 9, with id: 4569024208\n",
      "node with value 0, with id: 4569025424\n",
      "node with value 1, with id: 4569026128\n",
      "end of list reached\n"
     ]
    }
   ],
   "source": [
    "# construct the head lists\n",
    "listA = myLinkedList(2)\n",
    "listA.append(4)\n",
    "listA.append(3)\n",
    "\n",
    "listB = myLinkedList(5)\n",
    "listB.append(6)\n",
    "listB.append(4)\n",
    "print(listA)\n",
    "print(listB)\n",
    "\n",
    "\n",
    "\n",
    "result = ListProblems.addTwoNumbers(listA.head, listB.head)\n",
    "print(result)\n",
    "\n",
    "\n",
    "# construct the head lists\n",
    "listA = myLinkedList(9)\n",
    "listA.append(9)\n",
    "listA.append(9)\n",
    "\n",
    "listB = myLinkedList(9)\n",
    "listB.append(9)\n",
    "print(listA)\n",
    "print(listB)\n",
    "\n",
    "result = ListProblems.addTwoNumbers(listA.head, listB.head)\n",
    "print(result)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.11.4"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}