5th Mar 2024 Linked_List_Assignment_2_Solution.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "caa3bc6c-4d60-4159-b49b-731edb3a3074",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Mar_5^24_Assignment_17_Linked_List_Assignment_2_Solution'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"Mar_5^24_Assignment_17_Linked_List_Assignment_2_Solution\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "d0497612-70ed-4d4d-b6f8-a06744260f3d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5->"
     ]
    }
   ],
   "source": [
    "#1.Define a doubly linked list[ Will be done in the class ]\n",
    "class Node:\n",
    "    def __init__(self,data=None,next=None,prev=None):\n",
    "        self.data=data\n",
    "        self.next=next\n",
    "        self.prev=prev\n",
    "class DoublyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head=None\n",
    "        self.tail=None\n",
    "    def addNode(self,data):\n",
    "        newNode=Node(data)\n",
    "        if self.head is None:\n",
    "            self.head=newNode\n",
    "            self.tail=newNode\n",
    "        else:\n",
    "            newNode.prev=self.tail\n",
    "            self.tail.next=newNode\n",
    "            self.tail=newNode\n",
    "    def traverse(self):\n",
    "        temp=self.head\n",
    "        while(temp):\n",
    "            print(temp.data,end=\"->\")\n",
    "            temp=temp.next\n",
    "dll=DoublyLinkedList()\n",
    "dll.addNode(1)\n",
    "dll.addNode(2)\n",
    "dll.addNode(3)\n",
    "dll.addNode(4)\n",
    "dll.addNode(5)\n",
    "dll.traverse()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "faa74881-0e44-44d4-8a70-cfad367cae55",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1->2->3->4->5->\n",
      "5->4->3->2->1->"
     ]
    }
   ],
   "source": [
    "#2.Write a function to reverse a linked list in-place.\n",
    "class Node:\n",
    "    def __init__(self,data=None,next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "def reverseLL(head):\n",
    "    curr=head\n",
    "    prev=None\n",
    "    while curr is not None:\n",
    "        next_node=curr.next\n",
    "        curr.next=prev\n",
    "        prev=curr\n",
    "        curr=next_node\n",
    "    head=prev\n",
    "    return head\n",
    "def traverse(head):\n",
    "    temp=head\n",
    "    while temp:\n",
    "        print(temp.data,end=\"->\")\n",
    "        temp=temp.next\n",
    "#Create a linked list>>Collection of link Nodes\n",
    "head=Node(1)\n",
    "node2=Node(2)\n",
    "node3=Node(3)\n",
    "node4=Node(4)\n",
    "node5=Node(5)\n",
    "#Create the linkage\n",
    "head.next=node2\n",
    "node2.next=node3\n",
    "node3.next=node4\n",
    "node4.next=node5\n",
    "traverse(head)\n",
    "print()\n",
    "rev_head=reverseLL(head)\n",
    "traverse(rev_head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "fbcfd7f5-b0a9-42a2-a52a-a59b753fdcaf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is cycle present: True\n"
     ]
    }
   ],
   "source": [
    "#3.Detect cicle in a linked list.\n",
    "class Node:\n",
    "    def __init__(self,data=None,next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "def isCyclePresent(head):\n",
    "    slow=head\n",
    "    fast=head\n",
    "    while(fast and fast.next):\n",
    "        slow=slow.next\n",
    "        fast=fast.next.next\n",
    "        if(fast and slow.data==fast.data):\n",
    "            return True\n",
    "    return False\n",
    "#Create a linked list>>Collection of link Nodes\n",
    "head=Node(1)\n",
    "node2=Node(2)\n",
    "node3=Node(3)\n",
    "node4=Node(4)\n",
    "node5=Node(5)\n",
    "#Create the linkage\n",
    "head.next=node2\n",
    "node2.next=node3\n",
    "node3.next=node4\n",
    "node4.next=node5\n",
    "node5.next=node2\n",
    "print(\"Is cycle present:\",isCyclePresent(head))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "0e9c4c76-21f0-4488-ac0a-10514dbd2b78",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linked list 1:\n",
      "1->3->5->7->\n",
      "Linked list 2:\n",
      "2->4->6->8->\n",
      "Merged Sorted Linked List:\n",
      "1->2->3->4->5->6->7->8->"
     ]
    }
   ],
   "source": [
    "'''4. Merge two sorted linked list into one\n",
    "1->3->5->7->null and 2->4->6->8->null should be merged to make\n",
    "1->2->3->4->5->6->7->8'''\n",
    "class Node:\n",
    "    def __init__(self,data=None,next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "def merge_sortedLL(head1,head2):\n",
    "    dummy=Node()\n",
    "    tail=dummy\n",
    "    while head1 and head2:\n",
    "        if head1.data<=head2.data:\n",
    "            tail.next=head1\n",
    "            head1=head1.next\n",
    "        else:\n",
    "            tail.next=head2\n",
    "            head2=head2.next\n",
    "        tail=tail.next\n",
    "    if head1:\n",
    "        tail.next=head1\n",
    "    else:\n",
    "        tail.next=head2\n",
    "    return dummy.next\n",
    "def traverse(head):\n",
    "    temp=head\n",
    "    while(temp):\n",
    "        print(temp.data,end=\"->\")\n",
    "        temp=temp.next\n",
    "#LL1\n",
    "head1=Node(1)\n",
    "head1.next=Node(3)\n",
    "head1.next.next=Node(5)\n",
    "head1.next.next.next=Node(7)\n",
    "#LL2\n",
    "head2=Node(2)\n",
    "head2.next=Node(4)\n",
    "head2.next.next=Node(6)\n",
    "head2.next.next.next=Node(8)\n",
    "print(\"Linked list 1:\")\n",
    "traverse(head1)\n",
    "print()\n",
    "print(\"Linked list 2:\")\n",
    "traverse(head2)\n",
    "print()\n",
    "merged_head=merge_sortedLL(head1,head2)\n",
    "print(\"Merged Sorted Linked List:\")\n",
    "traverse(merged_head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "8327f4e2-6b69-4555-a3cd-68c60e799fea",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input LL:\n",
      "1->2->3->4->5->6->\n",
      "Resulting LL:\n",
      "1->2->3->4->6->"
     ]
    }
   ],
   "source": [
    "'''5.Write a function to remove nth node from the end in a linked list\n",
    "1->2->3->4->5->6, removing 2nd node from end will return 1->2->3->4->6'''\n",
    "class Node:\n",
    "    def __init__(self,data=None,next=None):\n",
    "        self.data=data\n",
    "        self.next=next\n",
    "#Find the length of the linked list\n",
    "def length(head):\n",
    "    lenLL=0\n",
    "    while head:\n",
    "        lenLL+=1\n",
    "        head=head.next\n",
    "    return lenLL\n",
    "\n",
    "def remove_nth_from_end(head,n):\n",
    "    prev=None\n",
    "    curr=head\n",
    "    #Calculate the position of the node to be removed from the beginning (length-n)\n",
    "    for i in range(length(head)-n):\n",
    "        #Traverse the list to the node just before the node to be removed\n",
    "        prev=curr\n",
    "        curr=curr.next\n",
    "    #Update pointers to skip the node to be removed\n",
    "    if prev:\n",
    "        prev.next=curr.next\n",
    "    else:\n",
    "        head=curr.next\n",
    "    return head #Return the updated head of the linked list\n",
    "def traverse(head):\n",
    "    temp=head\n",
    "    while(temp):\n",
    "        print(temp.data,end=\"->\")\n",
    "        temp=temp.next\n",
    "#Create a linked list>>Collection of link Nodes\n",
    "head=Node(1)\n",
    "node2=Node(2)\n",
    "node3=Node(3)\n",
    "node4=Node(4)\n",
    "node5=Node(5)\n",
    "node6=Node(6)\n",
    "#Create the linkage\n",
    "head.next=node2\n",
    "node2.next=node3\n",
    "node3.next=node4\n",
    "node4.next=node5\n",
    "node5.next=node6\n",
    "print(\"Input LL:\")\n",
    "traverse(head)\n",
    "print()\n",
    "print(\"Resulting LL:\")\n",
    "r_head=remove_nth_from_end(head,2)\n",
    "traverse(r_head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ec99add3-4c35-4412-a2d3-bc8128c0468f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input LL:\n",
      "1->2->3->3->4->4->4->5->\n",
      "Output LL:\n",
      "1->2->3->4->5->"
     ]
    }
   ],
   "source": [
    "'''6.Remove duplicates from a sorted linked list\n",
    "1->2->3->3->4->4->4->5  should be changed to 1->2->3->4->5'''\n",
    "class ListNode:\n",
    "    def __init__(self,val=None,next=None):\n",
    "        self.val=val\n",
    "        self.next=next\n",
    "def remove_duplicates(head):\n",
    "    if not head:\n",
    "        return head\n",
    "    #Initialize the current\n",
    "    curr=head\n",
    "    #Check if any other element in the list\n",
    "    while(curr.next):\n",
    "        if curr.val==curr.next.val:\n",
    "            curr.next=curr.next.next\n",
    "        else:\n",
    "            curr=curr.next\n",
    "    return head\n",
    "def traverse(head):\n",
    "    temp=head\n",
    "    while(temp):\n",
    "        print(temp.val,end=\"->\")\n",
    "        temp=temp.next\n",
    "#Input LL\n",
    "head=ListNode(1)\n",
    "head.next=ListNode(2)\n",
    "head.next.next=ListNode(3)\n",
    "head.next.next.next=ListNode(3)\n",
    "head.next.next.next.next=ListNode(4)\n",
    "head.next.next.next.next.next=ListNode(4)\n",
    "head.next.next.next.next.next.next=ListNode(4)\n",
    "head.next.next.next.next.next.next.next=ListNode(5)\n",
    "print(\"Input LL:\")\n",
    "traverse(head)\n",
    "print()\n",
    "r_head=remove_duplicates(head)\n",
    "print(\"Output LL:\")\n",
    "traverse(r_head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "4c519ee0-310d-43ab-97bb-22b8c562c0b3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LinkedList1:\n",
      "1->2->3->4->8->6->9->\n",
      "LinkeList2:\n",
      "5->1->6->7->\n",
      "Intersecting Nodes:\n",
      "1->6->"
     ]
    }
   ],
   "source": [
    "'''7.Find the intersection of the two linked lists\n",
    "1->2->3->4->8->6->9  5->1->6->7  , intersection 1->6'''\n",
    "class ListNode:\n",
    "    def __init__(self,val=None,next=None):\n",
    "        self.val=val\n",
    "        self.next=next\n",
    "def Find_intersection(head1,head2):\n",
    "    if not head1 or not head2:\n",
    "        return None\n",
    "    \n",
    "    curr1,curr2=head1,head2\n",
    "    len1,len2=0,0\n",
    "    while(curr1):\n",
    "        len1+=1\n",
    "        curr1=curr1.next\n",
    "    while(curr2):\n",
    "        len2+=1\n",
    "        curr2=curr2.next\n",
    "    while(len1>len2):\n",
    "        head1=head1.next\n",
    "        len1-=1\n",
    "    while(len1<len2):\n",
    "        head2=head2.next\n",
    "        len2-=1\n",
    "    while(head1!=head2):\n",
    "        head1=head1.next\n",
    "        head2=head2.next\n",
    "    return head1\n",
    "def traverse(head):\n",
    "    temp=head\n",
    "    while(temp):\n",
    "        print(temp.val,end=\"->\")\n",
    "        temp=temp.next    \n",
    "#(Create LL1 the collection of ListNode 1)\n",
    "head1=ListNode(1)\n",
    "head1.next=ListNode(2)\n",
    "head1.next.next=ListNode(3)\n",
    "head1.next.next.next=ListNode(4)\n",
    "head1.next.next.next.next=ListNode(8)\n",
    "head1.next.next.next.next.next=ListNode(6)\n",
    "head1.next.next.next.next.next.next=ListNode(9)\n",
    "print(\"LinkedList1:\")\n",
    "traverse(head1)\n",
    "print()\n",
    "#Create LL2 the collection of ListNode 1\n",
    "head2=ListNode(5)\n",
    "head2.next=head1\n",
    "head2.next.next=head1.next.next.next.next.next\n",
    "head2.next.next.next=ListNode(7)\n",
    "print(\"LinkeList2:\")\n",
    "traverse(head2)\n",
    "print()\n",
    "head2.next.next.next=None\n",
    "print(\"Intersecting Nodes:\")\n",
    "traverse(Find_intersection(head1,head2))\n",
    "#Sir I have Tried Multiple ways, but Required Output has not come...But this is what i did, sorry if not right way!!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "760c998a-3972-4e66-913a-e61078d3f7df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial Linked List:\n",
      "1->2->3->4->8->6->9->\n",
      "Rotated Linked List:\n",
      "3->4->8->6->9->1->2->"
     ]
    }
   ],
   "source": [
    "'''8.Rotate a linked list by k positions to the right\n",
    "1->2->3->4->8->6->9 , after rotating for 2 times becomes , 3->4->8->6->9->1->2'''\n",
    "class Node:\n",
    "    def __init__(self, data=None, next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "\n",
    "def rotateLeft(head, k):\n",
    "    if not head or not head.next or k == 0:\n",
    "        return head\n",
    "    \n",
    "    # Find the length of the linked list\n",
    "    length = 1\n",
    "    tail = head\n",
    "    while tail.next:\n",
    "        tail = tail.next\n",
    "        length += 1\n",
    "    \n",
    "    # Calculate the actual rotation index\n",
    "    rotation_index = k % length\n",
    "    if rotation_index == 0:\n",
    "        return head\n",
    "    \n",
    "    # Find the node before the new head\n",
    "    new_head_index = rotation_index - 1\n",
    "    new_head = head\n",
    "    for i in range(new_head_index):\n",
    "        new_head = new_head.next\n",
    "    \n",
    "    # Perform the rotation\n",
    "    new_tail = new_head\n",
    "    while new_tail.next:\n",
    "        new_tail = new_tail.next\n",
    "    new_tail.next = head\n",
    "    head = new_head.next\n",
    "    new_head.next = None\n",
    "    \n",
    "    return head\n",
    "\n",
    "def traverse(head):\n",
    "    temp = head\n",
    "    while temp:\n",
    "        print(temp.data, end=\"->\")\n",
    "        temp = temp.next\n",
    "\n",
    "#Create the linked list\n",
    "#Create the linked list\n",
    "head = Node(1)\n",
    "head.next = Node(2)\n",
    "head.next.next = Node(3)\n",
    "head.next.next.next = Node(4)\n",
    "head.next.next.next.next = Node(8)\n",
    "head.next.next.next.next.next = Node(6)\n",
    "head.next.next.next.next.next.next = Node(9)\n",
    "\n",
    "#Print the initial linked list\n",
    "print(\"Initial Linked List:\")\n",
    "traverse(head)\n",
    "print()\n",
    "#Rotate the linked list to the left\n",
    "k = 2\n",
    "rotated_head = rotateLeft(head, k)\n",
    "#Print the rotated linked list\n",
    "print(\"Rotated Linked List:\")\n",
    "traverse(rotated_head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "be13406f-9fa7-4076-a89c-efb7c7116651",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linked list1:\n",
      "2->4->3->\n",
      "Linked list2:\n",
      "5->6->4->\n",
      "Sum of Linked list1 and list2:\n",
      "7->0->8->\n"
     ]
    }
   ],
   "source": [
    "'''9.Add Two Numbers Represented by LinkedLists:\n",
    "Given two non-empty linked lists representing two non-negative integers, where the digits are stored in\n",
    "reverse order, add the two numbers and return it as a linked list.'''\n",
    "class Node:\n",
    "    def __init__(self, data=None, next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "\n",
    "def addTwoNumbers(head1, head2):\n",
    "    dummy = Node()\n",
    "    current = dummy\n",
    "    carry = 0\n",
    "    \n",
    "    while head1 or head2 or carry:\n",
    "        sum = carry\n",
    "        \n",
    "        if head1:\n",
    "            sum += head1.data\n",
    "            head1 = head1.next\n",
    "        \n",
    "        if head2:\n",
    "            sum += head2.data\n",
    "            head2 = head2.next\n",
    "        \n",
    "        carry = sum // 10\n",
    "        current.next = Node(sum % 10)\n",
    "        current = current.next\n",
    "    \n",
    "    return dummy.next\n",
    "def traverse(head):\n",
    "    temp = head\n",
    "    while temp:\n",
    "        print(temp.data, end=\"->\")\n",
    "        temp = temp.next\n",
    "\n",
    "#Creating the first linked list\n",
    "head1 = Node(2)\n",
    "node2 = Node(4)\n",
    "node3 = Node(3)\n",
    "head1.next = node2\n",
    "node2.next = node3\n",
    "print(\"Linked list1:\")\n",
    "traverse(head1)\n",
    "print()\n",
    "#Creating the second linked list\n",
    "head2 = Node(5)\n",
    "node4 = Node(6)\n",
    "node5 = Node(4)\n",
    "head2.next = node4\n",
    "node4.next = node5\n",
    "print(\"Linked list2:\")\n",
    "traverse(head2)\n",
    "print()\n",
    "#Calling the addTwoNumbers function\n",
    "result = addTwoNumbers(head1, head2)\n",
    "print(\"Sum of Linked list1 and list2:\")\n",
    "traverse(result)\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "639345c9-e37f-4250-a054-53de5b11da74",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Linked List:\n",
      "Data: 1 Next: 2 Random: 3\n",
      "Data: 2 Next: 3 Random: 1\n",
      "Data: 3 Next: 4 Random: 4\n",
      "Data: 4 Next: None Random: 2\n",
      "\n",
      "Cloned Linked List:\n",
      "Data: 1 Next: 2 Random: 3\n",
      "Data: 2 Next: 3 Random: 1\n",
      "Data: 3 Next: 4 Random: 4\n",
      "Data: 4 Next: None Random: 2\n"
     ]
    }
   ],
   "source": [
    "'''10.Clone a Linked List with next and Random Pointer\n",
    "Given a linked list of size N where each node has two links: one pointer points to the next node and the\n",
    "second pointer points to any node in the list.The task is to create a clone of this linked list in O(N) time. \n",
    "Note: The pointer pointing to the next node is ‘next‘ pointer and the one pointing to an arbitrary node is\n",
    "called ‘arbit’ pointer as it can point to any arbitrary node in the linked list.'''\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, data=None,next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "        self.random = None\n",
    "\n",
    "#Function to clone a linked list with next and random pointers\n",
    "def cloneLinkedList(head):\n",
    "    if not head:\n",
    "        return None\n",
    "\n",
    "    #Create a hashmap to store the mapping between original and cloned nodes\n",
    "    node_map = {}\n",
    "\n",
    "    #Create a new head node for the cloned list\n",
    "    cloned_head = Node(head.data)\n",
    "    node_map[head] = cloned_head\n",
    "\n",
    "    #Traverse the original list\n",
    "    curr = head\n",
    "    cloned_curr = cloned_head\n",
    "\n",
    "    while curr:\n",
    "        #Clone the next pointer\n",
    "        if curr.next:\n",
    "            if curr.next not in node_map:\n",
    "                node_map[curr.next] = Node(curr.next.data)\n",
    "            cloned_curr.next = node_map[curr.next]\n",
    "\n",
    "        #Clone the random pointer\n",
    "        if curr.random:\n",
    "            if curr.random not in node_map:\n",
    "                node_map[curr.random] = Node(curr.random.data)\n",
    "            cloned_curr.random = node_map[curr.random]\n",
    "\n",
    "        #Move to the next node\n",
    "        curr = curr.next\n",
    "        cloned_curr = cloned_curr.next\n",
    "\n",
    "    return cloned_head\n",
    "#Create the original linked list\n",
    "node1 = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(4)\n",
    "\n",
    "node1.next = node2\n",
    "node2.next = node3\n",
    "node3.next = node4\n",
    "\n",
    "node1.random = node3\n",
    "node2.random = node1\n",
    "node3.random = node4\n",
    "node4.random = node2\n",
    "\n",
    "#Clone the linked list\n",
    "cloned_head = cloneLinkedList(node1)\n",
    "\n",
    "#Print the original and cloned linked lists\n",
    "print(\"Original Linked List:\")\n",
    "curr = node1\n",
    "while curr:\n",
    "    print(\"Data:\", curr.data, \"Next:\", curr.next.data if curr.next else None, \"Random:\", curr.random.data if curr.random else None)\n",
    "    curr = curr.next\n",
    "\n",
    "print(\"\\nCloned Linked List:\")\n",
    "cloned_curr = cloned_head\n",
    "while cloned_curr:\n",
    "    print(\"Data:\", cloned_curr.data, \"Next:\", cloned_curr.next.data if cloned_curr.next else None, \"Random:\", cloned_curr.random.data if cloned_curr.random else None)\n",
    "    cloned_curr = cloned_curr.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8894cb1-c2fe-4e17-b412-3bb4ee03e662",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}