Linked-List.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class node:\n",
    "    def __init__(self,data=None):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "\n",
    "class linked_list:\n",
    "    def __init__(self):\n",
    "        # the head node is not going to contain any data it will only used to referene the first node address\n",
    "        self.head=node() \n",
    "        self.length=0;\n",
    "        self.tail = self.head\n",
    "        \n",
    "\n",
    "    # Adds new node containing 'data' to the end of the linked list.\n",
    "    def append(self,data):\n",
    "        new_node=node(data)\n",
    "        cur=self.head\n",
    "        while cur.next!=None:\n",
    "            cur=cur.next\n",
    "        cur.next=new_node\n",
    "        self.length += 1\n",
    "        self.tail.next = new_node\n",
    "        self.tail = new_node\n",
    "        \n",
    "    def prepend(self,data):\n",
    "        new_node = node(data);\n",
    "        temp_node = self.head;\n",
    "        new_node.next = temp_node.next\n",
    "        self.head.next = new_node\n",
    "        self.length += 1\n",
    "         \n",
    "\n",
    "    # Returns the value of the node at 'index'.\n",
    "    def traverseToIndex(self,index):  \n",
    "        if(index >= self.length):\n",
    "            print('index out of bound')\n",
    "            return None\n",
    "        cur_node = self.head\n",
    "        curr_index = 0\n",
    "        while cur_node.next!=None:\n",
    "            cur_node=cur_node.next\n",
    "            if(curr_index == index): return cur_node.data\n",
    "            curr_index += 1\n",
    "\n",
    "    # Remove node \n",
    "    def remove(self,index):\n",
    "        if(index >= self.length):\n",
    "            print('index out of bound')\n",
    "            return None\n",
    "        cur_node = self.head\n",
    "        curr_index = 0\n",
    "        while cur_node.next!=None:\n",
    "            cur_node=cur_node.next\n",
    "            if(curr_index == index-1): \n",
    "                leader = cur_node\n",
    "                break;\n",
    "            curr_index += 1\n",
    "        \n",
    "        unwantedNode = leader.next\n",
    "        leader.next = unwantedNode.next\n",
    "        self.length -=1\n",
    "\n",
    "    def insertToIndex(self,index,data):\n",
    "        if(index >= self.length):\n",
    "            print('index out of bound')\n",
    "            return None\n",
    "        cur_node = self.head\n",
    "        curr_index = 0\n",
    "        while cur_node.next!=None:\n",
    "            cur_node=cur_node.next\n",
    "            if(curr_index == index-1): \n",
    "                leader = cur_node\n",
    "                break;\n",
    "            curr_index += 1\n",
    "        new_node=node(data)\n",
    "        holdingIndex = leader.next;\n",
    "        leader.next = new_node\n",
    "        new_node.next = holdingIndex\n",
    "        self.length +=1\n",
    "\n",
    "\n",
    "    # Returns the length (integer) of the linked list.\n",
    "    def getlength(self):\n",
    "        cur=self.head\n",
    "        total=0\n",
    "        while cur.next!=None:\n",
    "            total+=1\n",
    "            cur=cur.next\n",
    "        return total \n",
    "\n",
    "    # Prints out the linked list in traditional Python list format. \n",
    "    def display(self):\n",
    "        elems=[]\n",
    "        cur_node=self.head\n",
    "        while cur_node.next!=None:\n",
    "            cur_node=cur_node.next\n",
    "            elems.append(cur_node.data)\n",
    "        print(elems)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Length of linked list->  0\n",
      "[10, 2, 31]\n",
      "Length of linked list->  3\n",
      "[10, 2, 31, 23]\n",
      "Last Node Data-> 23\n",
      "First Node Data-> 10\n",
      "31\n",
      "Add data to index\n",
      "[10, 2, 10, 31, 23]\n",
      "Length of linked list->  5\n",
      "[10, 2, 10, 31]\n",
      "Length of linked list->  4\n",
      "[10, 10, 31]\n",
      "Length of linked list->  3\n",
      "10\n",
      "[100, 10, 10, 31]\n",
      "Length of linked list->  4\n",
      "[58, 100, 10, 10, 31]\n",
      "Length of linked list->  5\n"
     ]
    }
   ],
   "source": [
    "mylst = linked_list()\n",
    "print('Length of linked list-> ',mylst.length)\n",
    "mylst.append(10)\n",
    "mylst.append(2)\n",
    "mylst.append(31)\n",
    "mylst.display()\n",
    "print('Length of linked list-> ',mylst.getlength())\n",
    "mylst.append(23)\n",
    "mylst.display()\n",
    "print('Last Node Data->',mylst.tail.data)\n",
    "print('First Node Data->',mylst.head.next.data)\n",
    "print(mylst.traverseToIndex(2))\n",
    "print('Add data to index')\n",
    "mylst.insertToIndex(2,10)\n",
    "mylst.display()\n",
    "print('Length of linked list-> ',mylst.length)\n",
    "mylst.remove(4)\n",
    "mylst.display()\n",
    "print('Length of linked list-> ',mylst.length)\n",
    "mylst.remove(1)\n",
    "mylst.display()\n",
    "print('Length of linked list-> ',mylst.length)\n",
    "print(mylst.head.next.data)\n",
    "mylst.prepend(100)\n",
    "mylst.display()\n",
    "print('Length of linked list-> ',mylst.length)\n",
    "mylst.prepend(58)\n",
    "mylst.display()\n",
    "print('Length of linked list-> ',mylst.length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "You are given two non-empty linked lists representing two non-negative integers. \n",
    "The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.\n",
    "\n",
    "You may assume the two numbers do not contain any leading zero, except the number 0 itself.\n",
    "\n",
    "Example:\n",
    "\n",
    "Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)\n",
    "Output: 7 -> 0 -> 8\n",
    "Explanation: 342 + 465 = 807.\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "# Definition for singly-linked list\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:\n",
    "        print(l1,l2)\n",
    "        temp1 = l1\n",
    "        temp2 = l2\n",
    "        sumList = []\n",
    "        placeValue = 1\n",
    "        curr1=0\n",
    "        curr2=0\n",
    "        while temp1 != None:\n",
    "            curr1 += placeValue*temp1.val\n",
    "            placeValue *=10\n",
    "            temp1 = temp1.next\n",
    "        print(curr1)\n",
    "        \n",
    "        placeValue = 1\n",
    "        \n",
    "        while temp2 != None:\n",
    "            curr2 += placeValue*temp2.val\n",
    "            placeValue *=10\n",
    "            temp2 = temp2.next\n",
    "        lSum = curr1 + curr2\n",
    "        \n",
    "        \n",
    "        sumListNode = ListNode(lSum%10)\n",
    "        lSum //= 10\n",
    "        cur = sumListNode\n",
    "        while lSum > 0:\n",
    "            newNode = ListNode(lSum%10)\n",
    "            cur.next = newNode\n",
    "            cur = cur.next\n",
    "            lSum //= 10\n",
    "        print(sumListNode)\n",
    "        return sumListNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "1290. Convert Binary Number in a Linked List to Integer\n",
    "\n",
    "Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.\n",
    "Return the decimal value of the number in the linked list.\n",
    "\n",
    "Input: head = [1,0,1]\n",
    "Output: 5\n",
    "Explanation: (101) in base 2 = (5) in base 10\n",
    "\"\"\"\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def getDecimalValue(self, head: ListNode) -> int:\n",
    "        numList =[]\n",
    "        curr = head \n",
    "        while curr != None:\n",
    "            numList.append(curr.val)\n",
    "            curr = curr.next\n",
    "        # print(numList)\n",
    "        decimalNum = 0\n",
    "        decimalPower = 0\n",
    "        for val in reversed(numList):\n",
    "            if(val):\n",
    "                decimalNum += 2**decimalPower\n",
    "            decimalPower +=1\n",
    "        return decimalNum\n",
    "\n",
    "\n",
    "# driver code \n",
    "mainNode = ListNode(0);\n",
    "numList = [1,0,1]\n",
    "curr = mainNode;\n",
    "for i in numList:\n",
    "    newNode = ListNode(i)\n",
    "    curr.next = newNode;\n",
    "    curr = curr.next;\n",
    "\n",
    "sol = Solution()\n",
    "print(sol.getDecimalValue(mainNode.next))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 4 5 "
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "876. Middle of the Linked List\n",
    "Given a non-empty, singly linked list with head node head, return a middle node of linked list.\n",
    "If there are two middle nodes, return the second middle node.\n",
    "\n",
    "Input: [1,2,3,4,5]\n",
    "Output: Node 3 from this list (Serialization: [3,4,5])\n",
    "The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).\n",
    "Note that we returned a ListNode object ans, such that:\n",
    "ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.\n",
    "\"\"\"\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def middleNode(self, head: ListNode) -> ListNode:\n",
    "        curr = head;\n",
    "        nodeCount = 0\n",
    "        while curr != None:\n",
    "            nodeCount += 1\n",
    "            curr = curr.next\n",
    "            \n",
    "        middle = nodeCount//2\n",
    "        currNodeCount = 0\n",
    "        curr = head;\n",
    "        while curr != None:\n",
    "            if currNodeCount == middle:\n",
    "                head = curr\n",
    "                return head\n",
    "            curr = curr.next\n",
    "            currNodeCount+=1\n",
    "            \n",
    "# driver code \n",
    "mainNode = ListNode(0);\n",
    "numList = [1,2,3,4,5]\n",
    "curr = mainNode;\n",
    "for i in numList:\n",
    "    newNode = ListNode(i)\n",
    "    curr.next = newNode;\n",
    "    curr = curr.next;\n",
    "\n",
    "sol = Solution()\n",
    "node=sol.middleNode(mainNode.next)\n",
    "\n",
    "while node != None:\n",
    "    print(node.val,end=\" \")\n",
    "    node = node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2->3->6->7->1->5->4->NULL\n"
     ]
    }
   ],
   "source": [
    "# Definition for singly-linked list.\n",
    "\"\"\"\n",
    "328. Odd Even Linked List\n",
    "\n",
    "Given a singly linked list, group all odd nodes together followed by the even nodes. \n",
    "Please note here we are talking about the node number and not the value in the nodes.\n",
    "You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.\n",
    "\n",
    "Input: 1->2->3->4->5->NULL\n",
    "Output: 1->3->5->2->4->NULL\n",
    "\n",
    "Input: 2->1->3->5->6->4->7->NULL\n",
    "Output: 2->3->6->7->1->5->4->NULL\n",
    "\n",
    "Note:\n",
    "The relative order inside both the even and odd groups should remain as it was in the input.\n",
    "The first node is considered odd, the second node even and so on ...\n",
    "\"\"\"\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if head == None :\n",
    "            return head\n",
    "        oddList = []\n",
    "        evenList = []\n",
    "        curr = head;\n",
    "        nodeCount = 1\n",
    "        while curr != None:\n",
    "            if nodeCount & 1 :\n",
    "                oddList.append(curr.val)\n",
    "            else:\n",
    "                evenList.append(curr.val)\n",
    "            curr = curr.next\n",
    "            nodeCount += 1\n",
    "#         print(oddList)\n",
    "#         print(evenList)\n",
    "        finalNodeList = oddList + evenList \n",
    "        # print(finalNodeList)\n",
    "        head = ListNode(finalNodeList[0])\n",
    "        curr = head\n",
    "        \n",
    "        for i in range(1,len(finalNodeList)):\n",
    "            newNode = ListNode(finalNodeList[i])\n",
    "            curr.next = newNode;\n",
    "            curr = curr.next;\n",
    "        return head\n",
    "            \n",
    "            \n",
    "# driver code \n",
    "mainNode = ListNode(0);\n",
    "numList = [2,1,3,5,6,4,7]\n",
    "curr = mainNode;\n",
    "for i in numList:\n",
    "    newNode = ListNode(i)\n",
    "    curr.next = newNode;\n",
    "    curr = curr.next;\n",
    "\n",
    "sol = Solution()\n",
    "result = sol.oddEvenList(mainNode.next)\n",
    "curr = result \n",
    "while curr != None:\n",
    "    print(curr.val,end=\"->\");\n",
    "    if curr.next == None:\n",
    "        print('NULL')\n",
    "    curr = curr.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7->4->6->5->3->1->2->NULL\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "206. Reverse Linked List\n",
    "Reverse a singly linked list.\n",
    "\n",
    "Input: 1->2->3->4->5->NULL\n",
    "Output: 5->4->3->2->1->NULL\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def reverseList(self, head: ListNode) -> ListNode:\n",
    "        prev = None\n",
    "        current = head \n",
    "        while(current is not None): \n",
    "            next = current.next\n",
    "            current.next = prev \n",
    "            prev = current \n",
    "            current = next\n",
    "        head = prev\n",
    "        return head\n",
    "        \n",
    "\n",
    "# driver code \n",
    "mainNode = ListNode(0);\n",
    "numList = [2,1,3,5,6,4,7]\n",
    "curr = mainNode;\n",
    "for i in numList:\n",
    "    newNode = ListNode(i)\n",
    "    curr.next = newNode;\n",
    "    curr = curr.next;\n",
    "\n",
    "sol = Solution()\n",
    "result = sol.reverseList(mainNode.next)\n",
    "curr = result \n",
    "while curr != None:\n",
    "    print(curr.val,end=\"->\");\n",
    "    if curr.next == None:\n",
    "        print('NULL')\n",
    "    curr = curr.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}