Linked_list_assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "17bada34-091a-4a05-8a93-12100d85e9ff",
   "metadata": {},
   "source": [
    "12-03-2024, Linked_List_Assignment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "aea2c52b-e582-42d3-a8b2-47fd86e49050",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A double linked list is a type of data structure that consists of a sequence of elements called nodes. Each node contains two pointers or references: one that points to the previous node in the sequence previous pointer and one that points to the next node in the sequence next pointer.\n",
      "\n",
      "class Node:\n",
      "    def __init__(self, data):\n",
      "        self.data = data\n",
      "        self.prev = None\n",
      "        self.next = None\n",
      "\n",
      "class DoublyLinkedList:\n",
      "    def __init__(self):\n",
      "        self.head = None\n",
      "\n",
      "    def append(self, data):\n",
      "        new_node = Node(data)\n",
      "        if not self.head:\n",
      "            self.head = new_node\n",
      "        else:\n",
      "            current = self.head\n",
      "            while current.next:\n",
      "                current = current.next\n",
      "            current.next = new_node\n",
      "            new_node.prev = current\n",
      "\n",
      "    def prepend(self, data):\n",
      "        new_node = Node(data)\n",
      "        if not self.head:\n",
      "            self.head = new_node\n",
      "        else:\n",
      "            new_node.next = self.head\n",
      "            self.head.prev = new_node\n",
      "            self.head = new_node\n",
      "\n",
      "    def print_list(self):\n",
      "        current = self.head\n",
      "        while current:\n",
      "            print(current.data, end=\" \")\n",
      "            current = current.next\n",
      "        print()\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(\"A double linked list is a type of data structure that consists of a sequence of elements called nodes. Each node contains two pointers or references: one that points to the previous node in the sequence previous pointer and one that points to the next node in the sequence next pointer.\")\n",
    "print()\n",
    "print('''class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.prev = None\n",
    "        self.next = None\n",
    "\n",
    "class DoublyLinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "\n",
    "    def append(self, data):\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "        else:\n",
    "            current = self.head\n",
    "            while current.next:\n",
    "                current = current.next\n",
    "            current.next = new_node\n",
    "            new_node.prev = current\n",
    "\n",
    "    def prepend(self, data):\n",
    "        new_node = Node(data)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "        else:\n",
    "            new_node.next = self.head\n",
    "            self.head.prev = new_node\n",
    "            self.head = new_node\n",
    "\n",
    "    def print_list(self):\n",
    "        current = self.head\n",
    "        while current:\n",
    "            print(current.data, end=\" \")\n",
    "            current = current.next\n",
    "        print()\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "0cf8e89c-e40b-4f9f-a916-0035ba6157f4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "class Node:\n",
      "    def __init__(self, data):\n",
      "        self.data = data\n",
      "        self.next = None\n",
      "\n",
      "def reverse_linked_list(head):\n",
      "    prev_node = None\n",
      "    current_node = head\n",
      "\n",
      "    while current_node:\n",
      "        next_node = current_node.next\n",
      "        current_node.next = prev_node\n",
      "        prev_node = current_node\n",
      "        current_node = next_node\n",
      "\n",
      "    return prev_node\n",
      "\n",
      "def print_linked_list(head):\n",
      "    current_node = head\n",
      "    while current_node:\n",
      "        print(current_node.data, end=\" \")\n",
      "        current_node = current_node.next\n",
      "    print()\n",
      "\n",
      "head = Node(1)\n",
      "head.next = Node(2)\n",
      "head.next.next = Node(3)\n",
      "head.next.next.next = Node(4)\n",
      "\n",
      "print(\"Original linked list:\")\n",
      "print_linked_list(head)\n",
      "\n",
      "head = reverse_linked_list(head)\n",
      "\n",
      "print(\"Reversed linked list:\")\n",
      "print_linked_list(head)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('''class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "def reverse_linked_list(head):\n",
    "    prev_node = None\n",
    "    current_node = head\n",
    "\n",
    "    while current_node:\n",
    "        next_node = current_node.next\n",
    "        current_node.next = prev_node\n",
    "        prev_node = current_node\n",
    "        current_node = next_node\n",
    "\n",
    "    return prev_node\n",
    "\n",
    "def print_linked_list(head):\n",
    "    current_node = head\n",
    "    while current_node:\n",
    "        print(current_node.data, end=\" \")\n",
    "        current_node = current_node.next\n",
    "    print()\n",
    "\n",
    "head = Node(1)\n",
    "head.next = Node(2)\n",
    "head.next.next = Node(3)\n",
    "head.next.next.next = Node(4)\n",
    "\n",
    "print(\"Original linked list:\")\n",
    "print_linked_list(head)\n",
    "\n",
    "head = reverse_linked_list(head)\n",
    "\n",
    "print(\"Reversed linked list:\")\n",
    "print_linked_list(head)\n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c58344be-9c2d-4382-a745-9b7f8f5f2a9e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "class Node:\n",
      "    def __init__(self, data):\n",
      "        self.data = data\n",
      "        self.next = None\n",
      "\n",
      "def has_cycle(head):\n",
      "    if head is None or head.next is None:\n",
      "        return False\n",
      "    \n",
      "    slow_pointer = head\n",
      "    fast_pointer = head.next\n",
      "\n",
      "    while fast_pointer and fast_pointer.next:\n",
      "        if slow_pointer == fast_pointer:\n",
      "            return True\n",
      "        slow_pointer = slow_pointer.next\n",
      "        fast_pointer = fast_pointer.next.next\n",
      "\n",
      "    return False\n",
      "\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 = head.next \n",
      "\n",
      "print(has_cycle(head))  \n",
      "\n",
      "head_no_cycle = Node(1)\n",
      "head_no_cycle.next = Node(2)\n",
      "head_no_cycle.next.next = Node(3)\n",
      "head_no_cycle.next.next.next = Node(4)\n",
      "\n",
      "print(has_cycle(head_no_cycle)) \n",
      "\n"
     ]
    }
   ],
   "source": [
    "print('''class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "def has_cycle(head):\n",
    "    if head is None or head.next is None:\n",
    "        return False\n",
    "    \n",
    "    slow_pointer = head\n",
    "    fast_pointer = head.next\n",
    "\n",
    "    while fast_pointer and fast_pointer.next:\n",
    "        if slow_pointer == fast_pointer:\n",
    "            return True\n",
    "        slow_pointer = slow_pointer.next\n",
    "        fast_pointer = fast_pointer.next.next\n",
    "\n",
    "    return False\n",
    "\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 = head.next \n",
    "\n",
    "print(has_cycle(head))  \n",
    "\n",
    "head_no_cycle = Node(1)\n",
    "head_no_cycle.next = Node(2)\n",
    "head_no_cycle.next.next = Node(3)\n",
    "head_no_cycle.next.next.next = Node(4)\n",
    "\n",
    "print(has_cycle(head_no_cycle)) \n",
    "''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "0e313259-f6c6-4723-9bda-915646e761ea",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First sorted linked list:\n",
      "1-->3-->5-->6\n",
      "Second sorted linked list:\n",
      "2-->4-->7-->8\n",
      "Merged sorted linked list:\n",
      "1-->2-->3-->4-->5-->6-->7-->8\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "def merge_sorted_lists(head1, head2):\n",
    "    if head1 is None:\n",
    "        return head2\n",
    "    if head2 is None:\n",
    "        return head1\n",
    "\n",
    "    dummy_node = Node(0)\n",
    "    merged_tail = dummy_node\n",
    "\n",
    "    while head1 and head2:\n",
    "        if head1.data <= head2.data:\n",
    "            merged_tail.next = head1\n",
    "            head1 = head1.next\n",
    "        else:\n",
    "            merged_tail.next = head2\n",
    "            head2 = head2.next\n",
    "        merged_tail = merged_tail.next\n",
    "\n",
    "\n",
    "    if head1:\n",
    "        merged_tail.next = head1\n",
    "    elif head2:\n",
    "        merged_tail.next = head2\n",
    "\n",
    "    return dummy_node.next\n",
    "\n",
    "def print_linked_list(head):\n",
    "    current_node = head\n",
    "    s=\"\"\n",
    "    while current_node:\n",
    "        s+=str(current_node.data) + '-->' if current_node.next else str(current_node.data)\n",
    "        current_node = current_node.next\n",
    "    print(s)\n",
    "\n",
    "list1_head = Node(1)\n",
    "list1_head.next = Node(3)\n",
    "list1_head.next.next = Node(5)\n",
    "list1_head.next.next.next = Node(6)\n",
    "\n",
    "list2_head = Node(2)\n",
    "list2_head.next = Node(4)\n",
    "list2_head.next.next = Node(7)\n",
    "list2_head.next.next.next = Node(8)\n",
    "\n",
    "print(\"First sorted linked list:\")\n",
    "print_linked_list(list1_head)\n",
    "\n",
    "print(\"Second sorted linked list:\")\n",
    "print_linked_list(list2_head)\n",
    "\n",
    "merged_head = merge_sorted_lists(list1_head, list2_head)\n",
    "\n",
    "print(\"Merged sorted linked list:\")\n",
    "print_linked_list(merged_head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "c828f56b-666b-48bf-b0bf-ce55108e6cdb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original linked list:\n",
      "1-->2-->3-->4-->5-->6\n",
      "After removing 2th element from the end:\n",
      "1-->2-->3-->4-->6\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def remove_nth_from_end(head, n):\n",
    "    dummy = Node(0)\n",
    "    dummy.next = head\n",
    "    slow = fast = dummy\n",
    "\n",
    "    for _ in range(n + 1):\n",
    "        fast = fast.next\n",
    "\n",
    "    while fast:\n",
    "        slow = slow.next\n",
    "        fast = fast.next\n",
    "\n",
    "    slow.next = slow.next.next\n",
    "\n",
    "    return dummy.next\n",
    "\n",
    "\n",
    "def printl(head2):\n",
    "    he = head2\n",
    "    s=\"\"\n",
    "    while he:\n",
    "        s+=str(he.data) + \"-->\" if he.next else str(he.data)\n",
    "        he = he.next\n",
    "    print(s)\n",
    "\n",
    "\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(5)\n",
    "head.next.next.next.next.next = Node(6)\n",
    "\n",
    "n = 2\n",
    "print(\"Original linked list:\")\n",
    "printl(head)\n",
    "\n",
    "head = remove_nth_from_end(head, n)\n",
    "\n",
    "print(f\"After removing {n}th element from the end:\")\n",
    "printl(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "5bb864e5-f2fa-467f-a8d5-53bcf3111e19",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original linked list:\n",
      "1-->2-->3-->3-->4-->4-->4-->5\n",
      "After removing duplicates:\n",
      "1-->2-->3-->4-->5\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def remove_duplicates(head):\n",
    "    l=[]\n",
    "    h = head\n",
    "    while h:\n",
    "        a = h.data\n",
    "        if a not in l:\n",
    "            l.append(a)\n",
    "            h = h.next\n",
    "        else:\n",
    "            h = h.next\n",
    "    \n",
    "    head0 = Node(l[0])\n",
    "    curr = head0\n",
    "    for val in l[1:]:\n",
    "        curr.next = Node(val)\n",
    "        curr = curr.next\n",
    "    return head0\n",
    "    \n",
    "def printl(head2):\n",
    "    he = head2\n",
    "    s=\"\"\n",
    "    while he:\n",
    "        s+=str(he.data) + \"-->\" if he.next else str(he.data)\n",
    "        he = he.next\n",
    "    print(s)\n",
    "\n",
    "\n",
    "values = [1, 2, 3, 3, 4, 4, 4, 5]\n",
    "head = Node(values[0])\n",
    "current = head\n",
    "for val in values[1:]:\n",
    "    current.next = Node(val)\n",
    "    current = current.next\n",
    "\n",
    "n = 2\n",
    "print(\"Original linked list:\")\n",
    "printl(head)\n",
    "\n",
    "head1 = remove_duplicates(head)\n",
    "\n",
    "print(f\"After removing duplicates:\")\n",
    "printl(head1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "7bfe54bd-4ec7-4e7d-a21e-0c48578ff3f0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1-->6\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def find_inter(head1, head2):\n",
    "    result = Node(0)\n",
    "    r = result\n",
    "    a = head1\n",
    "    h = head2\n",
    "    while a:\n",
    "        b = head2\n",
    "        while b:\n",
    "            if a.data == b.data:\n",
    "                ans = a.data\n",
    "                r.next = Node(ans)\n",
    "                r = r.next\n",
    "                b = b.next\n",
    "            else:\n",
    "                b = b.next\n",
    "        b = h\n",
    "        a = a.next\n",
    "    return result.next\n",
    "    \n",
    "def printl(head):\n",
    "    m = head\n",
    "    s=\"\"\n",
    "    while m:\n",
    "        s+= str(m.data) + \"-->\" if m.next else str(m.data)\n",
    "        m = m.next\n",
    "    print(s)\n",
    "    \n",
    "values1 = [1, 2, 3, 4, 8, 6, 9]\n",
    "head1 = Node(values1[0])\n",
    "current = head1\n",
    "for val in values1[1:]:\n",
    "    current.next = Node(val)\n",
    "    current = current.next\n",
    "    \n",
    "values2 = [5, 1, 6, 7]\n",
    "head2 = Node(values2[0])\n",
    "current = head2\n",
    "for val in values2[1:]:\n",
    "    current.next = Node(val)\n",
    "    current = current.next\n",
    "\n",
    "head0 = find_inter(head1, head2)\n",
    "printl(head0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "925d5a28-8da9-42ff-9fe3-dc6a0f96f67b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter how many rotations: 2\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3-->4-->8-->6-->9-->1-->2\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "def rotate(head,n):\n",
    "    re = Node(0)\n",
    "    ma = re\n",
    "    h = head\n",
    "    i=0\n",
    "    while i < n:\n",
    "        b=h.data\n",
    "        ma.next = Node(b)\n",
    "        ma = ma.next\n",
    "        h = h.next\n",
    "        i+=1\n",
    "    result = Node(0)\n",
    "    fin = result\n",
    "    while h:\n",
    "        fin.next = Node(h.data)\n",
    "        fin = fin.next\n",
    "        h = h.next\n",
    "    f=re.next\n",
    "    while f:\n",
    "        fin.next = Node(f.data)\n",
    "        fin = fin.next\n",
    "        f = f.next\n",
    "        \n",
    "    return result.next\n",
    "    \n",
    "def printl(head):\n",
    "    m = head\n",
    "    s=\"\"\n",
    "    while m:\n",
    "        s+= str(m.data) + \"-->\" if m.next else str(m.data)\n",
    "        m = m.next\n",
    "    print(s)\n",
    "    \n",
    "values = [1, 2, 3, 4, 8, 6, 9]\n",
    "head = Node(values[0])\n",
    "current = head\n",
    "for val in values[1:]:\n",
    "    current.next = Node(val)\n",
    "    current = current.next\n",
    "\n",
    "n=int(input(\"Enter how many rotations:\"))\n",
    "\n",
    "head0 = rotate(head,n)\n",
    "printl(head0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "8f56ea1f-d091-4ab5-ac51-b70ff0234788",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 -> 0 -> 8 -> "
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "def addTwoNumbers(l1, l2):\n",
    "    dummy = ListNode() \n",
    "    current = dummy\n",
    "    carry = 0\n",
    "    \n",
    "    while l1 or l2 or carry:\n",
    "        val1 = l1.val if l1 else 0\n",
    "        val2 = l2.val if l2 else 0\n",
    "        total = val1 + val2 + carry\n",
    "        \n",
    "        carry = total // 10\n",
    "        \n",
    "        current.next = ListNode(total % 10)\n",
    "        current = current.next\n",
    "        \n",
    "        if l1:\n",
    "            l1 = l1.next\n",
    "        if l2:\n",
    "            l2 = l2.next\n",
    "    \n",
    "    return dummy.next \n",
    "\n",
    "l1 = ListNode(2, ListNode(4, ListNode(3)))\n",
    "l2 = ListNode(5, ListNode(6, ListNode(4)))\n",
    "\n",
    "result = addTwoNumbers(l1, l2)\n",
    "while result:\n",
    "    print(result.val, end=\" -> \")\n",
    "    result = result.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "493ff83c-1c46-41b0-bff8-7633f5c46ab8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Data: 1 Arbit Data: 3\n",
      "Data: 2 Arbit Data: 1\n",
      "Data: 3 Arbit Data: 2\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        self.next = None\n",
    "        self.arbit = None\n",
    "\n",
    "def clone_linked_list(head):\n",
    "    if not head:\n",
    "        return None\n",
    "    \n",
    "    curr = head\n",
    "    while curr:\n",
    "        new_node = Node(curr.data)\n",
    "        new_node.next = curr.next\n",
    "        curr.next = new_node\n",
    "        curr = new_node.next\n",
    "    \n",
    "    curr = head\n",
    "    while curr:\n",
    "        if curr.arbit:\n",
    "            curr.next.arbit = curr.arbit.next\n",
    "        curr = curr.next.next\n",
    "    \n",
    "    original_head = head\n",
    "    clone_head = head.next\n",
    "    clone_curr = clone_head\n",
    "    \n",
    "    while original_head:\n",
    "        original_head.next = clone_curr.next\n",
    "        original_head = original_head.next\n",
    "        \n",
    "        if original_head:\n",
    "            clone_curr.next = original_head.next\n",
    "            clone_curr = clone_curr.next\n",
    "    \n",
    "    return clone_head\n",
    "\n",
    "original_head = Node(1)\n",
    "original_head.next = Node(2)\n",
    "original_head.next.next = Node(3)\n",
    "\n",
    "original_head.arbit = original_head.next.next\n",
    "original_head.next.arbit = original_head\n",
    "original_head.next.next.arbit = original_head.next\n",
    "\n",
    "cloned_head = clone_linked_list(original_head)\n",
    "\n",
    "while cloned_head:\n",
    "    print(\"Data:\", cloned_head.data, \"Arbit Data:\", cloned_head.arbit.data if cloned_head.arbit else None)\n",
    "    cloned_head = cloned_head.next\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2d6444cc-5931-44bb-ad00-feb19761f337",
   "metadata": {},
   "source": [
    "THANK YOU FOR GIVING THIS ASSIGNMENT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f68e129d-436a-4e9b-98b4-be6d2f7f24b6",
   "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
}