Linked_List_Implimentations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Some well-known questions and answers to linked lists. \n",
    "\n",
    "# See more advanced implimentations can be downloaded from the data structures and algorithms-1 repository \n",
    "# https://github.com/volkansonmez/Algorithms-and-Data-Structures-1\n",
    "\n",
    "# Finding middle element in a linked list\n",
    "# Reverse a linked list\n",
    "# Reverse a Linked List in groups of given size\n",
    "# Intersection point in Y shaped linked lists\n",
    "# Detect Loop in linked list\n",
    "# Remove loop in Linked List\n",
    "# Merge two sorted linked lists\n",
    "# Intersection point of two Linked Lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(<__main__.LinkedList at 0x1160a2450>, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "class LinkedList():\n",
    "    def __init__(self, head = None):\n",
    "        self.head = head\n",
    "\n",
    "    \n",
    "    def add_node_to_head(self, value):\n",
    "        if self.head == None:\n",
    "            new_node = Node(value)\n",
    "            self.head = new_node\n",
    "        else:\n",
    "            tmp = self.head\n",
    "            new_node = Node(value)\n",
    "            self.head = new_node\n",
    "            self.head.next = tmp\n",
    "        \n",
    "        \n",
    "    def add_node_to_tail(self, value):\n",
    "        if self.head == None:\n",
    "            new_node = Node(value)\n",
    "            self.head = new_node\n",
    "        else:\n",
    "            key_node = self.head\n",
    "            while key_node.next != None:\n",
    "                key_node = key_node.next\n",
    "            new_node = Node(value)\n",
    "            key_node.next = new_node\n",
    "            \n",
    "    \n",
    "    def delete_head_node(self):\n",
    "        if self.head == None: return\n",
    "        elif self.head.next == None: \n",
    "            self.head = None\n",
    "        else:\n",
    "            self.head = self.head.next\n",
    "            \n",
    "            \n",
    "    def delete_tail_node(self):\n",
    "        if self.head == None: return\n",
    "        elif self.head.next == None:\n",
    "            self.head = None\n",
    "        else:\n",
    "            prev_node = self.head\n",
    "            key_node = self.head.next\n",
    "            while key_node.next != None:\n",
    "                key_node = key_node.next\n",
    "                prev_node = prev_node.next\n",
    "            # now key_node is the last node \n",
    "            prev_node.next = None\n",
    "        \n",
    "        \n",
    "    def print_nodes(self): # print cargos of each node from head to tail\n",
    "        key_node = self.head\n",
    "        while key_node != None:\n",
    "            print('cargo', key_node.cargo)\n",
    "            key_node = key_node.next\n",
    "        \n",
    "        \n",
    "      \n",
    "    def finding_middle_element(self):\n",
    "        length_of_the_list = self.find_length()\n",
    "        if length_of_the_list == 0: return None\n",
    "        key_node = self.head\n",
    "        # if the length is odd there will be one element\n",
    "        if length_of_the_list % 2 == 1: \n",
    "            for i in range(length_of_the_list // 2):\n",
    "                key_node = key_node.next\n",
    "            return key_node.cargo\n",
    "        else: # if the length is even, there will be two middle elements\n",
    "            for i in range((length_of_the_list // 2)-1):\n",
    "                key_node = key_node.next\n",
    "            return key_node.cargo , key_node.next.cargo\n",
    "        \n",
    "    \n",
    "    def reverse_linked_list(self):\n",
    "        # create a new linked list\n",
    "        new_list = LinkedList()\n",
    "        # traverse through the original linked list and insert each item to the head of the new linked list\n",
    "        if self.head == None: return\n",
    "        key_node = self.head\n",
    "        while key_node != None:\n",
    "            new_list.add_node_to_head(key_node.cargo)\n",
    "            key_node = key_node.next\n",
    "        return new_list\n",
    "            \n",
    "    \n",
    "    def find_length(self):\n",
    "        if self.head == None: return 0\n",
    "        length = 0\n",
    "        key_node = self.head\n",
    "        while key_node != None:\n",
    "            key_node = key_node.next\n",
    "            length += 1\n",
    "        return length\n",
    "    \n",
    "         \n",
    "    def reverse_in_k_groups(self,k):\n",
    "        if k <=1: return\n",
    "        reversed_list = []\n",
    "        sub_list = []\n",
    "        key_node = self.head\n",
    "        i = 0\n",
    "        while key_node.next != None:\n",
    "            sub_list.insert(0,key_node.cargo)\n",
    "            i += 1\n",
    "            key_node = key_node.next\n",
    "            if i % k == 0:\n",
    "                reversed_list.extend(sub_list)\n",
    "                sub_list = []\n",
    "        # for the last n items that are not inserted\n",
    "        reversed_list.extend(sub_list)\n",
    "        new_list = LinkedList()\n",
    "        for i in reversed_list:\n",
    "            new_list.add_node_to_tail(i)\n",
    "        return new_list , reversed_list # to view the list's values\n",
    "            \n",
    "        \n",
    "    def intersection_point_of_two_lists(self):\n",
    "        first_linked_list = LinkedList()\n",
    "        # add values to first linked list\n",
    "        for i in range(0,10):\n",
    "            first_linked_list.add_node_to_tail(i)\n",
    "        second_linked_list = LinkedList()\n",
    "        for i in range(10,15):\n",
    "            second_linked_list.add_node_to_tail(i)\n",
    "        # make an intersection point, a random number that is in the first list\n",
    "        second_linked_list.add_node_to_tail(7)\n",
    "        if first_linked_list.head == None: return\n",
    "        if second_linked_list.head == None: return\n",
    "        key_node1 = first_linked_list.head\n",
    "        key_node2 = second_linked_list.head\n",
    "        a_dict = {}\n",
    "        while key_node1 != None:\n",
    "            if key_node1.cargo in a_dict:\n",
    "                print('loop at', key_node1.cargo)\n",
    "            else:\n",
    "                a_dict[key_node1.cargo] = 'seen once'\n",
    "            key_node1 = key_node1.next\n",
    "        while key_node2 != None:\n",
    "            if key_node2.cargo in a_dict:\n",
    "                print('intersection', key_node2.cargo)\n",
    "            else:\n",
    "                a_dict[key_node2.cargo] = 'seen once'\n",
    "            key_node2 = key_node2.next\n",
    "            \n",
    "        \n",
    "            \n",
    "    def remove_loop(self):\n",
    "        # have two signals one for previous and one for current\n",
    "        # find the loop and mark its cargo with the current signal, have the previous.next assigned to None.\n",
    "        if self.head == None: return\n",
    "        if self.head.next == None: return\n",
    "        prev_node = self.head\n",
    "        curr_node = self.head.next\n",
    "        a_dict = {}\n",
    "        while curr_node != None and prev_node != None:\n",
    "            if curr_node.cargo in a_dict.keys():\n",
    "                print('{} seen twice'.format(curr_node.cargo))\n",
    "                # curr_node has been there, by-pass the current node\n",
    "                prev_node.next = None\n",
    "                return\n",
    "            else:\n",
    "                a_dict[curr_node.cargo] = 'seen once'\n",
    "                curr_node = curr_node.next\n",
    "                prev_node = prev_node.next\n",
    "            \n",
    "            \n",
    "    def merge_two_sorted_linked_lists(self): # 0-10 odd numbers and even numbers are merged\n",
    "        # create the first linked list\n",
    "        LL1 = LinkedList()\n",
    "        for i in range(0,10,2):\n",
    "            LL1.add_node_to_tail(i)\n",
    "        # create the second linked list\n",
    "        LL2 = LinkedList()\n",
    "        for i in range(1,10,2):\n",
    "            LL2.add_node_to_tail(i)\n",
    "        key_node1 = LL1.head\n",
    "        key_node2 = LL2.head\n",
    "        merged_cargo = []\n",
    "        while key_node1 != None and key_node2 != None:\n",
    "            if key_node1.cargo < key_node2.cargo:\n",
    "                merged_cargo.append(key_node1.cargo)\n",
    "                key_node1 = key_node1.next\n",
    "            elif key_node1.cargo > key_node2.cargo:\n",
    "                merged_cargo.append(key_node2.cargo)\n",
    "                key_node2 = key_node2.next\n",
    "            else:\n",
    "                merged_cargo.append(key_node1.cargo)\n",
    "                merged_cargo.append(key_node2.cargo)\n",
    "                key_node1 = key_node1.next\n",
    "                key_node2 = key_node2.next\n",
    "            if key_node1 == None:\n",
    "                while key_node2 != None:\n",
    "                    merged_cargo.append(key_node2.cargo)\n",
    "                    key_node2 = key_node2.next\n",
    "            if key_node2 == None:\n",
    "                while key_node1 != None:\n",
    "                    merged_cargo.append(key_node1.cargo)\n",
    "                    key_node1 = key_node1.next\n",
    "        merged_list = LinkedList()\n",
    "        for i in merged_cargo:\n",
    "            merged_list.add_node_to_tail(i)\n",
    "        return merged_list, merged_cargo\n",
    "                \n",
    "        \n",
    "    \n",
    "        \n",
    "class Node():\n",
    "    def __init__(self, cargo = None, next = None):\n",
    "        self.cargo = cargo\n",
    "        self.next = next\n",
    "\n",
    "       \n",
    "        \n",
    "test_list = LinkedList()\n",
    "# for i in range(0,8):\n",
    "#     test_list.add_node_to_tail(i)\n",
    "# test_list.add_node_to_tail(5)\n",
    "# test_list.add_node_to_tail(11)\n",
    "# for i in range(3):\n",
    "#     test_list.add_node_to_head(i)\n",
    "# test_list.delete_tail_node()\n",
    "# test_list.delete_tail_node()\n",
    "# test_list.delete_tail_node()\n",
    "# test_list.delete_tail_node()\n",
    "# test_list.print_nodes()\n",
    "# print('length', test_list.find_length())\n",
    "# print(test_list.finding_middle_element())\n",
    "# reversed_linked_list = test_list.reverse_linked_list()\n",
    "# reversed_linked_list.print_nodes()\n",
    "#print(test_list.reverse_in_groups_of_k(3))\n",
    "#print(test_list.reverse_in_k_groups(3))\n",
    "#test_list.intersection_point_of_two_lists()\n",
    "#test_list.remove_loop()\n",
    "test_list.merge_two_sorted_linked_lists()"
   ]
  },
  {
   "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
}