LINKED LIST-2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### REVERSE LINKED LIST-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 -1\n",
      "5 4 3 2 1 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def printLL(head):\n",
    "    while head is not None:\n",
    "        print(str(head.data),end=' ')\n",
    "        head=head.next\n",
    "    return\n",
    "\n",
    "def reverse_ll1(head):\n",
    "    if head.next==None or head is None:\n",
    "        return head\n",
    "    \n",
    "    smallhead=reverse_ll1(head.next)\n",
    "    curr=smallhead\n",
    "    while curr.next is not None:\n",
    "        curr=curr.next\n",
    "    curr.next=head\n",
    "    head.next=None\n",
    "    return smallhead\n",
    "\n",
    "head,tail=take_input()\n",
    "headc=reverse_ll1(head)\n",
    "printLL(headc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### REVERSE LINKED LIST-2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 10 -1\n",
      "10 9 8 7 6 5 4 3 2 1 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def printLL(head):\n",
    "    while head is not None:\n",
    "        print(str(head.data),end=' ')\n",
    "        head=head.next\n",
    "    return\n",
    "\n",
    "def reverse_ll2(head):\n",
    "    if head.next is None:\n",
    "        return head,head\n",
    "    \n",
    "    SH,ST=reverse_ll2(head.next)\n",
    "    ST.next=head\n",
    "    head.next=None\n",
    "    ST=ST.next\n",
    "    return SH,ST\n",
    "\n",
    "head,tail=take_input()\n",
    "headc,tailc=reverse_ll2(head)\n",
    "printLL(headc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### REVERSE A PART OF A LINKED LIST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 -1\n",
      "6 5 4 3 2 1 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def printLL(head):\n",
    "    while head is not None:\n",
    "        print(str(head.data),end=' ')\n",
    "        head=head.next\n",
    "    return\n",
    "\n",
    "def reverse_a_part_ll(head,tail2):\n",
    "    if head==tail2:\n",
    "        return head,head\n",
    "    \n",
    "    SH,ST=reverse_a_part_ll(head.next,tail2)\n",
    "    ST.next=head\n",
    "    head.next=None\n",
    "    ST=ST.next\n",
    "    return SH,ST\n",
    "\n",
    "head,tail=take_input()\n",
    "headc,tailc=reverse_a_part_ll(head,head.next.next.next.next.next)\n",
    "printLL(headc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### REVERSE LINKED LIST-3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 -1\n",
      "8 7 6 5 4 3 2 1 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def printLL(head):\n",
    "    while head is not None:\n",
    "        print(str(head.data),end=' ')\n",
    "        head=head.next\n",
    "    return\n",
    "\n",
    "def reverse_ll3(head):\n",
    "    if head.next==None:\n",
    "        return head\n",
    "    \n",
    "    smallhead=reverse_ll3(head.next)\n",
    "    tail=head.next\n",
    "    tail.next=head\n",
    "    head.next=None\n",
    "    return smallhead\n",
    "\n",
    "head,tail=take_input()\n",
    "headc=reverse_ll3(head)\n",
    "printLL(headc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### REVERSE LINKED LIST-ITERATIVELY"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5\n",
      "None\n",
      "5 4 3 2 1 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def printLL(head):\n",
    "    while head is not None:\n",
    "        print(head.data,end=' ')\n",
    "        head=head.next    \n",
    "\n",
    "def  lenll(head):\n",
    "    count=0\n",
    "    while head is not None:\n",
    "        count=count+1\n",
    "        head=head.next\n",
    "    return count\n",
    "\n",
    "def reverse_lli(head):\n",
    "    i,lll=1,lenll(head)\n",
    "    rcurr=tail\n",
    "    while i<lll:\n",
    "        curr=head\n",
    "        for j in range(0,lll-i-1,1):\n",
    "            curr=curr.next\n",
    "        rcurr.next=curr\n",
    "        rcurr=rcurr.next        \n",
    "        i+=1\n",
    "    rcurr.next=None\n",
    "    return tail\n",
    "\n",
    "head,tail=take_input()\n",
    "print(tail.next)\n",
    "headc=reverse_lli(head)\n",
    "printLL(headc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MID POINT OF LINKED LIST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 -1\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def  lenll(head):\n",
    "    count=0\n",
    "    while head is not None:\n",
    "        count=count+1\n",
    "        head=head.next\n",
    "    return count\n",
    "\n",
    "def mid_ll(head):\n",
    "    lll=lenll(head)\n",
    "    count=0\n",
    "    if lll%2==0:\n",
    "        c=lll//2-1\n",
    "    else:\n",
    "        c=lll//2\n",
    "    while count<c:\n",
    "        head=head.next\n",
    "        count+=1\n",
    "    print(head.data)\n",
    "    return\n",
    "\n",
    "head,tail=take_input()\n",
    "mid_ll(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MERGE TWO SORTED LINKED LIST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 3 5 7 -1\n",
      "4 6 8 10 -1\n",
      "1 3 4 5 6 7 8 10 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def printLL(head):\n",
    "    while head is not None:\n",
    "        print(str(head.data),end=' ')\n",
    "        head=head.next\n",
    "    return\n",
    "\n",
    "def merge_ll(head1,head2):\n",
    "    if head1.data<head2.data:\n",
    "        new_head=head1\n",
    "        curr=new_head\n",
    "        head1=head1.next\n",
    "    else:\n",
    "        new_head=head2\n",
    "        curr=new_head\n",
    "        head2=head2.next\n",
    "    \n",
    "    while head1 is not None and head2 is not None:\n",
    "            if head1.data<head2.data:\n",
    "                temp=head1\n",
    "                curr.next=temp\n",
    "                head1=head1.next            \n",
    "            else:\n",
    "                temp=head2\n",
    "                curr.next=temp\n",
    "                head2=head2.next\n",
    "            curr=curr.next\n",
    "    while head1 is None and head2 is not None:\n",
    "        temp=head2\n",
    "        curr.next=temp\n",
    "        head2=head2.next\n",
    "        curr=curr.next\n",
    "    \n",
    "    while head1 is not None and head2 is None:\n",
    "        temp=head1\n",
    "        curr.next=temp\n",
    "        head1=head1.next\n",
    "        curr=curr.next\n",
    "        \n",
    "    return new_head               \n",
    "\n",
    "head1,tail1=take_input()\n",
    "head2,tail2=take_input()\n",
    "headc=merge_ll(head1,head2)\n",
    "printLL(headc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MERGE SORT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "71 59 50 21 90 50 44 84 81 18 -1\n",
      "18 21 44 50 50 59 71 81 84 90 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def printLL(head):\n",
    "    while head is not None:\n",
    "        print(str(head.data),end=' ')\n",
    "        head=head.next\n",
    "    return\n",
    "\n",
    "def  lenll(head):\n",
    "    count=0\n",
    "    while head is not None:\n",
    "        count=count+1\n",
    "        head=head.next\n",
    "    return count\n",
    "\n",
    "def merge_ll(head1,head2):\n",
    "    if head1.data<head2.data:\n",
    "        new_head=head1\n",
    "        curr=new_head\n",
    "        head1=head1.next\n",
    "    else:\n",
    "        new_head=head2\n",
    "        curr=new_head\n",
    "        head2=head2.next\n",
    "    \n",
    "    while head1 is not None and head2 is not None:\n",
    "            if head1.data<head2.data:\n",
    "                temp=head1\n",
    "                curr.next=temp\n",
    "                head1=head1.next            \n",
    "            else:\n",
    "                temp=head2\n",
    "                curr.next=temp\n",
    "                head2=head2.next\n",
    "            curr=curr.next\n",
    "    while head1 is None and head2 is not None:\n",
    "        temp=head2\n",
    "        curr.next=temp\n",
    "        head2=head2.next\n",
    "        curr=curr.next\n",
    "    \n",
    "    while head1 is not None and head2 is None:\n",
    "        temp=head1\n",
    "        curr.next=temp\n",
    "        head1=head1.next\n",
    "        curr=curr.next\n",
    "        \n",
    "    return new_head\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(1000)\n",
    "\n",
    "def merge_sortll(head,tail,lll):\n",
    "    if lll==0 or lll==1 or head==None:\n",
    "        return head\n",
    "        \n",
    "    c=lll//2\n",
    "    count,curr=0,head\n",
    "    \n",
    "    while count<(c-1):\n",
    "        curr=curr.next\n",
    "        count+=1\n",
    "    \n",
    "    h2=curr\n",
    "    h2=h2.next\n",
    "    curr.next=None\n",
    "    \n",
    "    if lll%2==0:\n",
    "        u1=merge_sortll(head,curr,c)\n",
    "        u2=merge_sortll(h2,tail,c)            \n",
    "    else:\n",
    "        u1=merge_sortll(head,curr,c)\n",
    "        u2=merge_sortll(h2,tail,c+1)                \n",
    "    \n",
    "    headm=merge_ll(u1,u2)\n",
    "    \n",
    "    return headm\n",
    "     \n",
    "head,tail=take_input()\n",
    "lll=lenll(head)\n",
    "headc=merge_sortll(head,tail,lll)\n",
    "printLL(headc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FIND A NODE IN A LINKED LIST-RECURSIVELY"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "def linearSearchRecursive(head, n,i):\n",
    "    if head==None:\n",
    "        return -1\n",
    "    \n",
    "    if head.data==n:\n",
    "        return i\n",
    "    \n",
    "    position=linearSearchRecursive(head.next, n,i+1)\n",
    "    \n",
    "    return position\n",
    "    \n",
    "def ll(arr):\n",
    "    if len(arr)==0:\n",
    "        return None\n",
    "    head = Node(arr[0])\n",
    "    last = head\n",
    "    for data in arr[1:]:\n",
    "        last.next = Node(data)\n",
    "        last = last.next\n",
    "    return head\n",
    "\n",
    "# Main\n",
    "from sys import setrecursionlimit\n",
    "setrecursionlimit(11000)\n",
    "# Read the link list elements including -1\n",
    "arr=list(int(i) for i in input().strip().split(' '))\n",
    "# Create a Linked list after removing -1 from list\n",
    "l,i = ll(arr[:-1]),0\n",
    "data=int(input())\n",
    "index = linearSearchRecursive(l, data,i)\n",
    "print(index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### EVEN AFTER ODD LINKED LIST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1458 291 1377 959 1275 1118 157 156 1407 873 835 1377 1592 129 386 877 1139 461 1880 1263 -1\n",
      "291 1377 959 1275 157 1407 873 835 1377 129 877 1139 461 1263 1458 1118 156 1592 386 1880 \n"
     ]
    }
   ],
   "source": [
    "# Problem ID 331 even after odd in a LL\n",
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "def arrange_LinkedList(head):\n",
    "    oh,ot,eh,et=None,None,None,None\n",
    "    while head is not None:\n",
    "        if head.data%2!=0:\n",
    "            if oh==None:\n",
    "                oh,ot=head,head\n",
    "            elif oh!=None:\n",
    "                ot.next=head\n",
    "                ot=ot.next\n",
    "            head=head.next\n",
    "        elif head.data%2==0:\n",
    "            if eh==None:\n",
    "                eh,et=head,head\n",
    "            elif eh!=None:\n",
    "                et.next=head\n",
    "                et=et.next\n",
    "            head=head.next\n",
    "    \n",
    "    et.next=None\n",
    "    \n",
    "    if oh==None:\n",
    "        return eh\n",
    "    elif eh==None:\n",
    "        return oh\n",
    "    else:\n",
    "        ot.next=eh\n",
    "        return oh\n",
    "\n",
    "def ll(arr):\n",
    "    if len(arr)==0:\n",
    "        return None\n",
    "    head = Node(arr[0])\n",
    "    last = head\n",
    "    for data in arr[1:]:\n",
    "        last.next = Node(data)\n",
    "        last = last.next\n",
    "    return head\n",
    "\n",
    "def printll(head):\n",
    "    while head:\n",
    "        print(head.data, end=' ')\n",
    "        head = head.next\n",
    "    print()\n",
    "\n",
    "# Main\n",
    "# Read the link list elements including -1\n",
    "arr=list(int(i) for i in input().strip().split(' '))\n",
    "# Create a Linked list after removing -1 from list\n",
    "l = ll(arr[:-1])\n",
    "l = arrange_LinkedList(l)\n",
    "printll(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DELETE EVERY N NODES AFTER M NODES"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 -1\n",
      "3\n",
      "4\n"
     ]
    },
    {
     "ename": "AttributeError",
     "evalue": "'NoneType' object has no attribute 'next'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-1-da7b2a103bba>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m     55\u001b[0m \u001b[0mm\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0minput\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     56\u001b[0m \u001b[0mn\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0minput\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 57\u001b[1;33m \u001b[0ml\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mskipMdeleteN\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ml\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mm\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mn\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     58\u001b[0m \u001b[0mprintll\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ml\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-1-da7b2a103bba>\u001b[0m in \u001b[0;36mskipMdeleteN\u001b[1;34m(head, M, N)\u001b[0m\n\u001b[0;32m     29\u001b[0m     \u001b[0mt2\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mt1\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     30\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 31\u001b[1;33m     \u001b[0mskipMdeleteN\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mt2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mM\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mN\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     32\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mhead\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     33\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-1-da7b2a103bba>\u001b[0m in \u001b[0;36mskipMdeleteN\u001b[1;34m(head, M, N)\u001b[0m\n\u001b[0;32m     21\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     22\u001b[0m     \u001b[1;32mwhile\u001b[0m \u001b[0mj\u001b[0m\u001b[1;33m<\u001b[0m\u001b[0mN\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 23\u001b[1;33m         \u001b[1;32mif\u001b[0m \u001b[0mt1\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnext\u001b[0m \u001b[1;32mis\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[1;32mNone\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     24\u001b[0m             \u001b[0mt1\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mt1\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mnext\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     25\u001b[0m         \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mAttributeError\u001b[0m: 'NoneType' object has no attribute 'next'"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "def skipMdeleteN(head, M, N):\n",
    "    if M==0 or N==0:\n",
    "        return\n",
    "    if head is None:\n",
    "        return \n",
    "    \n",
    "    t1=head\n",
    "    i=0\n",
    "    j=0\n",
    "    while i<M-1:\n",
    "        if t1 is not  None:\n",
    "            t1=t1.next\n",
    "        else:\n",
    "            return \n",
    "        i+=1\n",
    "        \n",
    "    while j<N:\n",
    "        if t1.next is not None:\n",
    "            t1.next=t1.next.next\n",
    "        else:\n",
    "            return\n",
    "        j+=1\n",
    "        \n",
    "    t2=t1.next\n",
    "    \n",
    "    skipMdeleteN(t2,M,N)\n",
    "    return head        \n",
    "\n",
    "def ll(arr):\n",
    "    if len(arr)==0:\n",
    "        return None\n",
    "    head = Node(arr[0])\n",
    "    last = head\n",
    "    for data in arr[1:]:\n",
    "        last.next = Node(data)\n",
    "        last = last.next\n",
    "    return head\n",
    "\n",
    "def printll(head):\n",
    "    while head:\n",
    "        print(head.data, end=' ')\n",
    "        head = head.next\n",
    "    print()\n",
    "\n",
    "# Main\n",
    "# Read the link list elements including -1\n",
    "arr=list(int(i) for i in input().strip().split(' '))\n",
    "# Create a Linked list after removing -1 from list\n",
    "l = ll(arr[:-1])\n",
    "m=int(input())\n",
    "n=int(input())\n",
    "l = skipMdeleteN(l, m, n)\n",
    "printll(l)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SWAP TWO NODES IN LINKED LIST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 -1\n",
      "5 0\n",
      "6 2 3 4 5 1 7 8 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "def printLL(head):\n",
    "    while head is not None:\n",
    "        print(str(head.data),end=' ')\n",
    "        head=head.next\n",
    "    return\n",
    "\n",
    "def swap(head, i, j):\n",
    "    count=0\n",
    "    curr=head\n",
    "    if j-i==1 and i==0:\n",
    "        while curr is not None:\n",
    "            if count==i:\n",
    "                c1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==j:\n",
    "                c2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            else:\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "                \n",
    "        c1.next=c2.next\n",
    "        c2.next=c1\n",
    "        head=c2\n",
    "        \n",
    "    elif i-j==1 and j==0:\n",
    "        while curr is not None:\n",
    "            if count==i:\n",
    "                c1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==j:\n",
    "                c2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            else:\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "                \n",
    "        c2.next=c1.next\n",
    "        c1.next=c2\n",
    "        head=c1    \n",
    "        \n",
    "    \n",
    "    elif j-i==1 and i!=0:\n",
    "        while curr is not None:\n",
    "            if count==(i-1):\n",
    "                p1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==i:\n",
    "                c1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==j:\n",
    "                c2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            else:\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "              \n",
    "        p1.next=c2\n",
    "        c1.next=c2.next\n",
    "        c2.next=c1\n",
    "        \n",
    "    elif i-j==1 and j!=0:\n",
    "        while curr is not None:\n",
    "            if count==i:\n",
    "                c1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==(j-1):\n",
    "                p2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==j:\n",
    "                c2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            else:\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "        p2.next=c1\n",
    "        c2.next=c1.next\n",
    "        c1.next=c2\n",
    "    \n",
    "    elif i==0:\n",
    "        while curr is not None:\n",
    "            if count==i:\n",
    "                c1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==(j-1):\n",
    "                p2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==j:\n",
    "                c2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            else:\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "                \n",
    "        temp=c2.next\n",
    "        p2.next=c1\n",
    "        c2.next=c1.next\n",
    "        c1.next=temp\n",
    "        head=c2\n",
    "        \n",
    "    elif j==0:\n",
    "        while curr is not None:\n",
    "            if count==i:\n",
    "                c1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==(i-1):\n",
    "                p1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==j:\n",
    "                c2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            else:\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "                \n",
    "        temp=c1.next\n",
    "        p1.next=c2\n",
    "        c1.next=c2.next\n",
    "        c2.next=temp\n",
    "        head=c1    \n",
    "    \n",
    "    else:\n",
    "        while curr is not None:\n",
    "            if count==(i-1):\n",
    "                p1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==i:\n",
    "                c1=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==(j-1):\n",
    "                p2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            elif count==j:\n",
    "                c2=curr\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "            else:\n",
    "                count+=1\n",
    "                curr=curr.next\n",
    "                \n",
    "        temp=c1.next\n",
    "        p1.next=c2\n",
    "        p2.next=c1\n",
    "        c1.next=c2.next\n",
    "        c2.next=temp\n",
    "    \n",
    "    return head\n",
    "\n",
    "head,tail=take_input()\n",
    "i,j=[int(x) for x in input().split()]\n",
    "headc=swap(head, i, j)\n",
    "printLL(headc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### K REVERSE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 7 8 9 10 -1\n",
      "4\n",
      "4 3 2 1 8 7 6 5 10 9 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,data):\n",
    "        self.data=data\n",
    "        self.next=None\n",
    "        \n",
    "def take_input():\n",
    "    input_list=[int(x) for x in input().split()]\n",
    "    head=None\n",
    "    tail=None\n",
    "    for curr_data in input_list:\n",
    "        if curr_data==-1:\n",
    "            break\n",
    "            \n",
    "        new_node=node(curr_data)\n",
    "        if head is None:\n",
    "            head=new_node\n",
    "            tail=new_node     \n",
    "        else:\n",
    "            tail.next=new_node\n",
    "            tail=new_node\n",
    "            \n",
    "    return head,tail\n",
    "\n",
    "\n",
    "def print_reverse(head,tail2):\n",
    "    if head==tail2:\n",
    "        print(head.data,end=' ')\n",
    "        return\n",
    "    print_reverse(head.next,tail2)\n",
    "    print(head.data,end=' ')\n",
    "    return\n",
    "\n",
    "def  lenll(head):\n",
    "    count=0\n",
    "    while head is not None:\n",
    "        count=count+1\n",
    "        head=head.next    \n",
    "    return count\n",
    "\n",
    "def k_reverse(head,tail,k):\n",
    "    lll=lenll(head)\n",
    "    if k>lll:\n",
    "        print_reverse(head,tail)\n",
    "    else:\n",
    "        thead,ttail=head,head\n",
    "        while thead is not None:\n",
    "            count=1\n",
    "            while count<k:\n",
    "                if ttail.next==None:\n",
    "                    break\n",
    "                else:\n",
    "                    ttail=ttail.next\n",
    "                    count+=1           \n",
    "            print_reverse(thead,ttail)\n",
    "            ttail=ttail.next\n",
    "            thead=ttail           \n",
    "    return    \n",
    "\n",
    "head,tail=take_input()\n",
    "k=int(input())\n",
    "headc=k_reverse(head,tail,k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BUBBLE SORT IN LINKED LIST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 1 8 5 3 -1\n",
      "1 3 4 5 8 \n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "def bubbleSortLL(head) :\n",
    "    lll=lenll(head)\n",
    "    i=0\n",
    "    while i<lll:\n",
    "        curr,pre=head,None\n",
    "        j=0\n",
    "        while j<(lll-i-1):\n",
    "            if curr.data>curr.next.data:\n",
    "                if j==0:\n",
    "                    temp=curr.next\n",
    "                    curr.next=temp.next\n",
    "                    temp.next=curr\n",
    "                    head=temp\n",
    "                    pre=head\n",
    "                else:\n",
    "                    temp=curr.next\n",
    "                    pre.next=temp\n",
    "                    curr.next=temp.next\n",
    "                    temp.next=curr\n",
    "                    pre=pre.next                                \n",
    "            elif curr.data<=curr.next.data:\n",
    "                if j==0:\n",
    "                    pre=head\n",
    "                    curr=curr.next\n",
    "                else:\n",
    "                    pre=pre.next\n",
    "                    curr=curr.next\n",
    "            j+=1\n",
    "        i+=1\n",
    "    return head\n",
    "\n",
    "def  lenll(head):\n",
    "    count=0\n",
    "    while head is not None:\n",
    "        count=count+1\n",
    "        head=head.next    \n",
    "    return count    \n",
    "    \n",
    "def ll(arr):\n",
    "    if len(arr)==0:\n",
    "        return None\n",
    "    head = Node(arr[0])\n",
    "    last = head\n",
    "    for data in arr[1:]:\n",
    "        last.next = Node(data)\n",
    "        last = last.next\n",
    "    return head\n",
    "\n",
    "def printll(head):\n",
    "    while head:\n",
    "        print(head.data, end=' ')\n",
    "        head = head.next\n",
    "    print()\n",
    "\n",
    "# Main\n",
    "# Read the link list elements including -1\n",
    "arr=list(int(i) for i in input().strip().split(' '))\n",
    "# Create a Linked list after removing -1 from list\n",
    "l = ll(arr[:-1])\n",
    "l = bubbleSortLL(l)\n",
    "printll(l)"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}