Data_Structure_Linked_List.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Print element of linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Node(object):\n",
    " \n",
    "   def __init__(self, data=None, next_node=None):\n",
    "       self.data = data\n",
    "       self.next = next_node\n",
    " \n",
    " \n",
    "\n",
    "def print_list(head):\n",
    "    while head:\n",
    "        print(head.data)\n",
    "        head = head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insert element at the tail of a linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Insert(head, data):\n",
    "    # new = Node(data)\n",
    "    tail = Node(data)\n",
    "    if head == None:\n",
    "        head = tail\n",
    "        return head\n",
    "    else:\n",
    "        buff = head\n",
    "        while head.next:\n",
    "        # print(buff.data)\n",
    "            head = head.next\n",
    "        head.next = tail\n",
    "        head = buff\n",
    "        return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insert element at the head of a linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Insert(head, data):\n",
    "    node = Node(data)\n",
    "    node.next = head\n",
    "    head = node\n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Insert a node at a specific position in a linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def InsertNth(head, data, position):\n",
    "    node = Node(data)\n",
    "    if head == None: \n",
    "        head = node\n",
    "        return head\n",
    "    elif position == 0: # insert at head\n",
    "        node.next = head\n",
    "        head = node\n",
    "        return head\n",
    "    else:\n",
    "        count = 0\n",
    "        buff = head\n",
    "        while head:\n",
    "            count += 1\n",
    "            if count == position: #find the position to insert the node\n",
    "                node.next = head.next\n",
    "                head.next = node\n",
    "            head = head.next\n",
    "            # count += 1\n",
    "        head = buff\n",
    "        return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Delete a node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Delete(head, position):\n",
    "    if position == 0: # delete the head\n",
    "        head = head.next\n",
    "        return head\n",
    "    else:\n",
    "        count = 0\n",
    "        buff = head\n",
    "        prev = head\n",
    "        while head:\n",
    "            # count += 1\n",
    "            if count == position:    # find the node to be deleted\n",
    "                prev.next = head.next\n",
    "            prev = head\n",
    "            head = head.next\n",
    "            count += 1\n",
    "        head = buff\n",
    "        return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Print in reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ReversePrint(head):\n",
    "    if head == None:\n",
    "        return\n",
    "    else:\n",
    "        ReversePrint(head.next)\n",
    "        print(head.data)\n",
    "        \n",
    "        \n",
    "        \n",
    "def ReversePrint(head):\n",
    "    arr = []\n",
    "    while head:\n",
    "        arr.append(head.data)\n",
    "        head = head.next\n",
    "    for i in range(len(arr)-1,-1,-1):\n",
    "        print arr[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reverse the linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Reverse(head):\n",
    "    if head == None or head.next == None:\n",
    "        return head\n",
    "    else:\n",
    "        prev = Node(None)\n",
    "        prev.next = head\n",
    "        Next = head.next\n",
    "        while Next:\n",
    "            head.next = Next.next\n",
    "            if prev.data == None:\n",
    "                prev = Next\n",
    "                prev.next = head\n",
    "            else:\n",
    "                Next.next = prev\n",
    "                prev = Next\n",
    "            Next = head.next\n",
    "        head = prev\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Reverse(head):\n",
    "\n",
    "    prev_node = None\n",
    "    next_node = head\n",
    "    \n",
    "    while next_node:\n",
    "        copy_prev_node = prev_node\n",
    "        copy_next_next_node = next_node.next\n",
    "        \n",
    "        prev_node = next_node\n",
    "        next_node.next = copy_prev_node\n",
    "        next_node = copy_next_next_node\n",
    "    \n",
    "    head = prev_node\n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare two linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def CompareLists(headA, headB):\n",
    "    if not headA or not headB: #one of them is none or both of them are none\n",
    "        return headA == headB\n",
    "    else: #none of them is none, compare the current data\n",
    "        current_data = headA.data == headB.data\n",
    "        return int(current_data and CompareLists(headA.next, headB.next)) #current data matches, check the next data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Merge two sorted linked lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def MergeLists(headA, headB):\n",
    "        \n",
    "    if headA == None:\n",
    "        return headB\n",
    "    if headB == None:\n",
    "        return headA\n",
    "        \n",
    "    if headA.data >= headB.data:\n",
    "        smallernode = headB\n",
    "        smallernode.next = MergeLists(headA, headB.next)\n",
    "    else:\n",
    "        smallernode = headA\n",
    "        smallernode.next = MergeLists(headA.next, headB)\n",
    "        \n",
    "    return smallernode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get node value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def GetNode(head, position):\n",
    "    \n",
    "    if head == None:\n",
    "        return\n",
    "    \n",
    "    bf1 = head\n",
    "    bf2 = head\n",
    "    count = 0\n",
    "    \n",
    "    while count<position: # move bf2 ahead of bf1 with \"position\" length so when bf2 reach tail, bf1 is the node with position from trail\n",
    "        bf2 = bf2.next\n",
    "        #if bf2 == None:\n",
    "        #    return bf1\n",
    "        count +=1\n",
    "        \n",
    "    while bf2.next:\n",
    "        bf1 = bf1.next\n",
    "        bf2 = bf2.next\n",
    "        \n",
    "    return bf1.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Delete duplicate-value nodes from a sorted linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def RemoveDuplicates(head):\n",
    "    if head == None:\n",
    "        return\n",
    "    buff = head\n",
    "    while head:\n",
    "        Next = head.next\n",
    "        while Next and Next.data == head.data:\n",
    "            Next = Next.next\n",
    "        head.next = Next\n",
    "        head = head.next\n",
    "\n",
    "    return buff"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cycle detection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def has_cycle(head):\n",
    "    if head == None:\n",
    "        return\n",
    "    sn = head # slow node\n",
    "    qn = head # quick node\n",
    "    \n",
    "    while sn and qn:\n",
    "        sn = sn.next # slow node move one position at a time\n",
    "        if sn == None:\n",
    "            return 0\n",
    "        \n",
    "        qn = qn.next # quick node move two positions at a time\n",
    "        if qn == None:\n",
    "            return 0\n",
    "        qn = qn.next\n",
    "        if qn == None:\n",
    "            return 0\n",
    "        \n",
    "        if qn == sn: #If there is a cycle, quick node will eventually catch up with slow node\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find merge point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Say one list is x long and merges at j. And the other list is y long and merges at k.\n",
    "\n",
    "One iterator will take j steps to hit the merge point, then x-j steps to hit the end, \n",
    "then it will go to the other list and take k steps to hit the merge point. Total1 = j + (x-j) + k.\n",
    "\n",
    "The other iterator will take k steps to hit the merge, y-k to hit the end, \n",
    "then will go to the other list and take j steps to hit the merge. Total2 = k + (y-k) + j.\n",
    "\n",
    "Since the second part of both lists is the same sequence, x-j is the same as y-k. \n",
    "Call that number q. Plugging that into both totals gives j + q + k for the first and k + q + j for the second. \n",
    "Which are obviously equal. So they travel to the merge point in the same number of steps.\n",
    "\"\"\"\n",
    "\n",
    "def FindMergeNode(headA, headB):\n",
    "    \n",
    "    if headA == None or headB == None:\n",
    "        return\n",
    "    \n",
    "    curA = headA\n",
    "    curB = headB\n",
    "    \n",
    "    while curA != curB:\n",
    "        if curA.next == None:\n",
    "            curA = headB\n",
    "        else:\n",
    "            curA = curA.next\n",
    "        if curB.next == None:\n",
    "            curB = headA\n",
    "        else:\n",
    "            curB = curB.next\n",
    "    \n",
    "    return curA.data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inserting a Node Into a Sorted Doubly Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def SortedInsert(head, data):\n",
    "    \n",
    "    node = Node(data)\n",
    "    \n",
    "    if head == None:\n",
    "        return node\n",
    "\n",
    "    elif head.data >= node.data: #add to the head\n",
    "        head.prev = node\n",
    "        node.next = head\n",
    "        return node\n",
    "    \n",
    "    n2 = head\n",
    "    n1 = head\n",
    "    while n2 and n2.data < node.data:\n",
    "        n1 = n2\n",
    "        n2 = n2.next\n",
    "    \n",
    "    # node.next = head\n",
    "\n",
    "    if n2 == None: #add to the tail\n",
    "        n1.next = node\n",
    "        node.prev = n1\n",
    "    else:                 #add somewhere in the middle\n",
    "        n1.next = node\n",
    "        node.prev = n1\n",
    "        node.next = n2\n",
    "        n2.prev = node\n",
    "    \n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reverse a doubly linked list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Reverse(head):\n",
    "    if head == None or head.next == None:\n",
    "        return head\n",
    "    \n",
    "    node = head\n",
    "    n1 = None\n",
    "    n2 = None\n",
    "    while node:\n",
    "        # if node.next:\n",
    "        n1 = node.next\n",
    "        temp = node.prev\n",
    "        node.prev = node.next\n",
    "        node.next = temp\n",
    "        n2 = node\n",
    "        node = n1\n",
    "        \n",
    "    return n2"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}