Linked-List.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def driverCode(numList):\n",
    "    \"\"\"Driver code for linked List\"\"\"\n",
    "    mainNode = ListNode(0);\n",
    "    curr = mainNode;\n",
    "    for i in numList:\n",
    "        newNode = ListNode(i)\n",
    "        curr.next = newNode;\n",
    "        curr = curr.next;\n",
    "    return mainNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Url -> https://practice.geeksforgeeks.org/problems/finding-middle-element-in-a-linked-list/1\n",
    "\n",
    "Finding middle element in a linked list\n",
    "\n",
    "Given a singly linked list of N nodes. The task is to find middle of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.\n",
    "If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.\n",
    "\n",
    "Input:\n",
    "First line of input contains number of testcases T. For each testcase, first line of input contains length of linked list and next line contains data of nodes of linked list.\n",
    "\n",
    "Output:\n",
    "For each testcase, there will be a single line of output containing data of middle element of linked list.\n",
    "\n",
    "User Task:\n",
    "The task is to complete the function getMiddle() which takes head reference as the only argument and should return the data at the middle node of linked list.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <= N <= 100\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "5\n",
    "1 2 3 4 5\n",
    "6\n",
    "2 4 6 7 5 1\n",
    "\n",
    "Output:\n",
    "3\n",
    "7\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: Since, there are 5 elements, therefore 3 is the middle element at index 2 (0-based indexing).\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 Findingmiddleelementinalinkedlist(self, head: ListNode) -> int:\n",
    "        curr = head\n",
    "        currList = []\n",
    "        while curr != None:\n",
    "#             print(curr.val)\n",
    "            currList.append(curr.val)\n",
    "            curr = curr.next\n",
    "        middle = len(currList)//2\n",
    "        return currList[middle]\n",
    "        \n",
    "\n",
    "# driver code \n",
    "numList = [1 ,2 ,3, 4, 5]\n",
    "numList1 = [2 ,4 ,6 ,7, 5, 1]\n",
    "\n",
    "mainNode = driverCode(numList)\n",
    "mainNode1 = driverCode(numList1)\n",
    "sol = Solution()\n",
    "print(sol.Findingmiddleelementinalinkedlist(mainNode.next))\n",
    "print(sol.Findingmiddleelementinalinkedlist(mainNode1.next))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "url -> https://practice.geeksforgeeks.org/problems/nth-node-from-end-of-linked-list/1\n",
    "\n",
    "Nth node from end of linked list\n",
    "\n",
    "Given a linked list consisting of L nodes and given a number N. The task is to find the Nth node from the end of the linked list.\n",
    "\n",
    "Input:\n",
    "First line of input contains number of testcase T. For each testcase, first line of input contains number of nodes in the linked list and the number N. Next line contains N nodes of linked list.\n",
    "\n",
    "Output:\n",
    "For each testcase, output the data of node which is at Nth distance from end.\n",
    "\n",
    "User Task:\n",
    "The task is to complete the function getNthFromLast() which takes two arguments: reference to head and N and you need to return Nth from end.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 200\n",
    "1 <= L <= 103\n",
    "1 <= N <= 103\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "9 2\n",
    "1 2 3 4 5 6 7 8 9\n",
    "4 5\n",
    "10 5 100 5\n",
    "Output:\n",
    "8\n",
    "-1\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: In the first example, there are 9 nodes in linked list and we need to find 2nd node from end.  2nd node from end os 8.  \n",
    "Testcase 2: In the second example, there are 4 nodes in linked list and we need to find 5th from end.  Since 'n' is more than number of nodes in linked list, output is -1.\n",
    "\"\"\"\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def Nthnodefromendoflinkedlist(self, head: ListNode,indexFromLast:int) -> int:\n",
    "        curr = head\n",
    "        currList = []\n",
    "        length = 0\n",
    "        while curr != None:\n",
    "#             print(curr.val)\n",
    "            currList.append(curr.val)\n",
    "            length +=1\n",
    "            curr = curr.next\n",
    "        if length < indexFromLast:\n",
    "            return -1\n",
    "        traversingIndex = length - indexFromLast\n",
    "        return currList[traversingIndex]\n",
    "        \n",
    "\n",
    "# driver code \n",
    "indexFromLast = 2\n",
    "numList = [1,2, 3, 4, 5, 6, 7, 8, 9]\n",
    "indexFromLast1 = 5\n",
    "numList1 = [10, 5, 100, 5]\n",
    "\n",
    "mainNode = driverCode(numList)\n",
    "mainNode1 = driverCode(numList1)\n",
    "sol = Solution()\n",
    "print(sol.Nthnodefromendoflinkedlist(mainNode.next,indexFromLast))\n",
    "print(sol.Nthnodefromendoflinkedlist(mainNode1.next,indexFromLast1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "\n",
    "Insert in a Sorted List\n",
    "\n",
    "Given a sorted singly linked list and a data, your task is to complete the function sortedInsert() that inserts the data in the linked list in sorted way i.e. order of the list doesn't changes.\n",
    "\n",
    "Input:\n",
    "The function takes 2 arguments as input, reference pointer to the head of the sorted single linked list and an integer data value which is to be inserted in the list.\n",
    "There are multiple test cases and for each test case the function will be called separately.\n",
    "\n",
    "Output:\n",
    "For each test output will be space separated integers denoting the values of the linked list.\n",
    "\n",
    "User Task:\n",
    "The task is to complete the function sortedInsert() which should insert the element in sorted Linked List.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <= N <= 104\n",
    "-99999 <= A[i] <= 99999, for each valid i\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "6\n",
    "25 36 47 58 69 80\n",
    "19\n",
    "2\n",
    "50 100\n",
    "75\n",
    "\n",
    "Output:\n",
    "19 25 36 47 58 69 80\n",
    "50 75 100\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: After inserting 19 at particular place, the linked list is like 19, 25, 36, 47, 58, 69, 80.\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def InsertinaSortedList(self, head: ListNode,k_val:int) -> int:\n",
    "        curr = head\n",
    "        currList = []\n",
    "        length = 0\n",
    "        while curr != None:\n",
    "#             print(curr.val)\n",
    "            currList.append(curr.val)\n",
    "            length +=1\n",
    "            curr = curr.next\n",
    "        if length < indexFromLast:\n",
    "            return -1\n",
    "        traversingIndex = length - indexFromLast\n",
    "        return currList[traversingIndex]\n",
    "        \n",
    "\n",
    "# driver code \n",
    "val_0 = 19\n",
    "numList = [25, 36, 47, 58, 69, 80]\n",
    "# val_1 = 5\n",
    "# numList1 = [10, 5, 100, 5]\n",
    "\n",
    "mainNode = driverCode(numList)\n",
    "# mainNode1 = driverCode(numList1)\n",
    "sol = Solution()\n",
    "print(sol.InsertinaSortedList(mainNode.next,val_0))\n",
    "# print(sol.InsertinaSortedList(mainNode1.next,val_1))\n"
   ]
  }
 ],
 "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.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}