Linked List.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color=\"hotpink\"> Linked List </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Design Linked List\n",
    "\n",
    "Design your implementation of the linked list. You can choose to use a singly or doubly linked list.<br>\n",
    "A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. <br>\n",
    "If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed. <br>\n",
    "\n",
    "Implement the MyLinkedList class: <br>\n",
    "* _MyLinkedList()_ : Initializes the MyLinkedList object.\n",
    "* _int get(int index)_ : Get the value of the indexth node in the linked list. If the index is invalid, return -1.\n",
    "* _void addAtHead(int val)_ : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.\n",
    "* _void addAtTail(int val)_ : Append a node of value val as the last element of the linked list.\n",
    "* _void addAtIndex(int index, int val)_ : Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.\n",
    "* _void deleteAtIndex(int index)_ : Delete the indexth node in the linked list, if the index is valid.\n",
    " \n",
    "_Example 1:_ <br>\n",
    "Input : <br>\n",
    "`[\"MyLinkedList\", \"addAtHead\", \"addAtTail\", \"addAtIndex\", \"get\", \"deleteAtIndex\", \"get\"]\n",
    "[[], [1], [3], [1, 2], [1], [1], [1]]` <br>\n",
    "Output: <br>\n",
    "`[null, null, null, null, 2, null, 3]` <br>\n",
    "Explanation: <br>\n",
    "MyLinkedList myLinkedList = new MyLinkedList(); <br>\n",
    "myLinkedList.addAtHead(1); <br>\n",
    "myLinkedList.addAtTail(3); <br>\n",
    "myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3 <br>\n",
    "myLinkedList.get(1);              // return 2 <br>\n",
    "myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3 <br>\n",
    "myLinkedList.get(1);              // return 3 <br>\n",
    " \n",
    "_Constraints:_ <br>\n",
    "* 0 <= index, val <= 1000\n",
    "* Please do not use the built-in LinkedList library.\n",
    "* At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.\n",
    "<br>\n",
    "\n",
    "**Cool now it's done after third attempt, errors :**\n",
    "* I'm not updating the head while deleting the very first node\n",
    "* I'm not updating the tail while deleting the last node\n",
    "* Above two problems cause to break the code as head or tail is not referenced to anything"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val=0):\n",
    "        self.val = val\n",
    "        self.next = None\n",
    "        \n",
    "        \n",
    "class MyLinkedList(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.size = 0\n",
    "        \n",
    "\n",
    "    def get(self, index):\n",
    "        \"\"\"\n",
    "        Get the value of the index-th node in the linked list. If the index is invalid, return -1.\n",
    "        :type index: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if index < 0 or index > self.size -1:\n",
    "            return -1\n",
    "        \n",
    "        ptr = self.head\n",
    "        i = 0\n",
    "        \n",
    "        while ptr:\n",
    "            if index == i:\n",
    "                return ptr.val\n",
    "            i += 1\n",
    "            ptr = ptr.next\n",
    "            \n",
    "        return -1\n",
    "        \n",
    "\n",
    "    def addAtHead(self, val):\n",
    "        \"\"\"\n",
    "        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.\n",
    "        :type val: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        node = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.tail = node\n",
    "        else:\n",
    "            node.next = self.head\n",
    "            \n",
    "        self.head = node\n",
    "        self.size += 1\n",
    "            \n",
    "\n",
    "    def addAtTail(self, val):\n",
    "        \"\"\"\n",
    "        Append a node of value val to the last element of the linked list.\n",
    "        :type val: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        node = Node(val)\n",
    "        \n",
    "        if self.tail:\n",
    "            self.tail.next = node\n",
    "        else:\n",
    "            self.head = node\n",
    "            \n",
    "        self.tail = node\n",
    "        self.size += 1\n",
    "        \n",
    "\n",
    "    def addAtIndex(self, index, val):\n",
    "        \"\"\"\n",
    "        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.\n",
    "        :type index: int\n",
    "        :type val: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        if not index:            #if index value is zero\n",
    "            self.addAtHead(val)\n",
    "            return\n",
    "        elif self.size == index:   #if index is equal to lenth of List\n",
    "            self.addAtTail(val)\n",
    "            return\n",
    "        elif self.size < index:\n",
    "            return\n",
    "        \n",
    "        i = 0\n",
    "        node = Node(val)\n",
    "        ptr = self.head\n",
    "        \n",
    "        while ptr:\n",
    "            if i == index - 1:\n",
    "                node.next = ptr.next\n",
    "                ptr.next = node\n",
    "                break\n",
    "            ptr = ptr.next\n",
    "            i += 1\n",
    "            \n",
    "        self.size += 1\n",
    "    \n",
    "\n",
    "    def deleteAtIndex(self, index):\n",
    "        \"\"\"\n",
    "        Delete the index-th node in the linked list, if the index is valid.\n",
    "        :type index: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        if index >= self.size or index < 0:\n",
    "            return\n",
    "        elif not index:\n",
    "            self.head = self.head.next\n",
    "        else:\n",
    "            i = 0\n",
    "            ptr = self.head\n",
    "\n",
    "            for i in range(index - 1):\n",
    "                ptr = ptr.next\n",
    "\n",
    "            ptr.next = ptr.next.next\n",
    "            if index == self.size-1:\n",
    "                self.tail = ptr\n",
    "        \n",
    "        self.size -= 1\n",
    "    \n",
    "    \n",
    "    \n",
    "#main\n",
    "obj = MyLinkedList()\n",
    "obj.addAtHead(30)\n",
    "obj.addAtHead(40)\n",
    "obj.addAtHead(50)\n",
    "obj.addAtIndex(3, 20)\n",
    "obj.addAtTail(10)\n",
    "obj.deleteAtIndex(0)\n",
    "obj.addAtTail(10)\n",
    "obj.deleteAtIndex(4)\n",
    "obj.deleteAtIndex(0)\n",
    "obj.deleteAtIndex(2)\n",
    "obj.addAtTail(10)\n",
    "obj.addAtHead(40)\n",
    "obj.addAtHead(50)\n",
    "\n",
    "print(\"Length of Linked list is \", obj.size)\n",
    "print(\"Linked List :\", end=\" \")\n",
    "for i in range(obj.size):\n",
    "    print(obj.get(i), \"->\", end=\" \")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List Cycle : *Floyd’s Cycle-Finding Algorithm* \n",
    "\n",
    "Given head, the head of a linked list, determine if the linked list has a cycle in it. <br>\n",
    "There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. <br>\n",
    "\n",
    "Return true if there is a cycle in the linked list. Otherwise, return false. <br>\n",
    "\n",
    "_Example 1:_ <br>\n",
    "Input: `head = [3,2,0,-4], pos = 1` <br>\n",
    "Output: true  <br>\n",
    "`3 -> 2 -> 0 -> -4 -> \n",
    "      ^ <- <- <- <- v `<br> \n",
    "Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).\n",
    "\n",
    "_Example 2:_ <br>\n",
    "Input: `head = [1,2], pos = 0` <br>\n",
    "Output: true <br>\n",
    "Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.\n",
    "\n",
    "_Example 3:_ <br>\n",
    "Input: `head = [1], pos = -1` <br>\n",
    "Output: false <br>\n",
    "Explanation: There is no cycle in the linked list.\n",
    " \n",
    "_Constraints:_ <br>\n",
    "* The number of the nodes in the list is in the range $[0, 10^4]$.\n",
    "* $-10^5 <= Node.val <= 10^5$\n",
    "* pos is -1 or a valid index in the linked-list.\n",
    " \n",
    "Follow up: Can you solve it using O(1) (i.e. constant) memory?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "def loopDetect(head):\n",
    "    \"\"\"\n",
    "    Using HashMap\n",
    "    Time complexity: O(n), only one traversal of the loop is needed.\n",
    "    Auxiliary Space: O(n), n is the space required to store the value in hashmap.\n",
    "    \"\"\"\n",
    "    s = set()\n",
    "    ptr = head\n",
    "    \n",
    "    while ptr:\n",
    "        if ptr in s:    # if we already have this node means a loop encounter\n",
    "            return True\n",
    "        s.add(ptr)\n",
    "        ptr = ptr.next\n",
    "        \n",
    "    return False\n",
    "\n",
    "\n",
    "def hasCycle(head):\n",
    "    \"\"\"\n",
    "    :type head: ListNode\n",
    "    :rtype: bool\n",
    "    Time complexity: O(n), only one traversal of the loop is needed.\n",
    "    Auxiliary Space:O(1), there is no space required.\n",
    "    \"\"\"\n",
    "    #using two pointer technique and Floyd’s Cycle-Finding Algorithm\n",
    "    slow_ptr = head\n",
    "    fast_ptr = head\n",
    "    \n",
    "    while slow_ptr and fast_ptr and fast_ptr.next:\n",
    "        slow_ptr = slow_ptr.next\n",
    "        fast_ptr = fast_ptr.next.next\n",
    "        if slow_ptr == fast_ptr:       # if loop is there two ptrs meet after some interval\n",
    "            return True\n",
    "    return False\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Intersection of Two Linked Lists\n",
    "\n",
    "Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.\n",
    "\n",
    "For example, the following two linked lists begin to intersect at node c1: <br>\n",
    "<img src='https://assets.leetcode.com/uploads/2021/03/05/160_statement.png' alt=\"Two linked list Intersection image\" width=500 height=500/>\n",
    "\n",
    "The test cases are generated such that there are no cycles anywhere in the entire linked structure.<br>\n",
    "Note that the linked lists must retain their original structure after the function returns.\n",
    "\n",
    "_Custom Judge:_ <br>\n",
    "The inputs to the judge are given as follows (your program is not given these inputs):\n",
    "* intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.\n",
    "* listA - The first linked list.\n",
    "* listB - The second linked list.\n",
    "* skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.\n",
    "* skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.\n",
    "<br>\n",
    "The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.\n",
    "\n",
    "_Example 1:_<br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/05/160_example_1_1.png\" alt=\"example1 img\" width=500 height=500 /> <br>\n",
    "Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 <br>\n",
    "Output: Intersected at '8' <br>\n",
    "Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).\n",
    "From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.\n",
    "<br>\n",
    "\n",
    "_Example 2:_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/05/160_example_2.png\" alt=\"img2 example\" width=500 height=500 /> <br>\n",
    "Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1<br>\n",
    "Output: Intersected at '2' <br>\n",
    "Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).\n",
    "From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.\n",
    "<br>\n",
    "\n",
    "_Example 3:_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/05/160_example_3.png\" alt=\"img3 example\" width=500 height=500 /> <br>\n",
    "Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 <br>\n",
    "Output: No intersection <br>\n",
    "Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.\n",
    "Explanation: The two lists do not intersect, so return null.\n",
    "<br>\n",
    "\n",
    "_Constraints:_ <br>\n",
    "* The number of nodes of listA is in the m.\n",
    "* The number of nodes of listB is in the n.\n",
    "* 0 <= m, n <= 3 * $10^4$\n",
    "* 1 <= Node.val <= $10^5$\n",
    "* 0 <= skipA <= m\n",
    "* 0 <= skipB <= n\n",
    "* intersectVal is 0 if listA and listB do not intersect.\n",
    "* intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getIntersectionNode(headA, headB):\n",
    "    \"\"\"\n",
    "    :type head1, head1: ListNode\n",
    "    :rtype: ListNode\n",
    "    Time and Space complexity : O(m+n)\n",
    "    \"\"\"\n",
    "    # using HashMap\n",
    "    s = set()\n",
    "    \n",
    "    ptr = headA\n",
    "    while ptr:\n",
    "        s. add(ptr)\n",
    "        ptr = ptr.next\n",
    "    \n",
    "    ptr = headB\n",
    "    while ptr:\n",
    "        if ptr in s:\n",
    "            return ptr\n",
    "        ptr = ptr.next\n",
    "    \n",
    "    return None\n",
    "\n",
    "\n",
    "\n",
    "def getIntersectionNode(headA, headB):\n",
    "    \"\"\"\n",
    "    :type head1, head1: ListNode\n",
    "    :rtype: ListNode\n",
    "    Time complexity: O(m+n)\n",
    "    Space Complexity: O(1)\n",
    "    \"\"\"\n",
    "    lenA = 0\n",
    "    lenB = 0\n",
    "    ptrA = headA\n",
    "    ptrB = headB\n",
    "    \n",
    "    while ptrA:    # find the length of ListA\n",
    "        lenA += 1\n",
    "        ptrA = ptrA.next\n",
    "    \n",
    "    while ptrB:    # find the length of ListB\n",
    "        lenB += 1\n",
    "        ptrB = ptrB.next\n",
    "    \n",
    "    differ = 0\n",
    "    large_list_ptr = None\n",
    "    small_list_ptrPtr = None\n",
    "\n",
    "    if lenA > lenB:\n",
    "        differ = lenA - lenB\n",
    "        large_list_ptr = headA\n",
    "        small_list_ptrPtr = headB\n",
    "    else:\n",
    "        differ = lenB - lenA\n",
    "        large_list_ptr = headB\n",
    "        small_list_ptrPtr = headA\n",
    "    \n",
    "    for i in range(differ):  # move the largeList ptr so that length to the intersect node is same from the smallLsit ptr\n",
    "        large_list_ptr = large_list_ptr.next\n",
    "    \n",
    "    while large_list_ptr and small_list_ptrPtr:\n",
    "        if large_list_ptr == small_list_ptrPtr:\n",
    "            return large_list_ptr\n",
    "        large_list_ptr = large_list_ptr.next\n",
    "        small_list_ptrPtr = small_list_ptrPtr.next\n",
    "    \n",
    "    return None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Remove Nth Node From End of List\n",
    "\n",
    "Given the head of a linked list, remove the nth node from the end of the list and return its head.\n",
    "\n",
    "_Example 1:_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg\" alt=\"example1\" width=500 height=500 /> <br>\n",
    "Input: head = [1,2,3,4,5], n = 2 <br>\n",
    "Output: [1,2,3,5] <br>\n",
    "\n",
    "_Example 2:_ <br>\n",
    "Input: head = [1], n = 1 <br>\n",
    "Output: [] <br>\n",
    "\n",
    "_Example 3:_ <br>\n",
    "Input: head = [1,2], n = 1 <br>\n",
    "Output: [1] <br>\n",
    " \n",
    "_Constraints:_ <br>\n",
    "* The number of nodes in the list is sz.\n",
    "* 1 <= sz <= 30\n",
    "* 0 <= Node.val <= 100\n",
    "* 1 <= n <= sz\n",
    " \n",
    "\n",
    "Follow up: Could you do this in one pass?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeNthFromEnd(head, n):\n",
    "    \"\"\"\n",
    "    :type head: ListNode\n",
    "    :type n: int\n",
    "    :rtype: ListNode\n",
    "    \"\"\"\n",
    "    size = 0\n",
    "    ptr = head\n",
    "\n",
    "    while ptr:\n",
    "        size += 1\n",
    "        ptr = ptr.next\n",
    "\n",
    "    differ = size - n\n",
    "    i = 0\n",
    "    ptr = head\n",
    "\n",
    "    while i < differ - 1:\n",
    "        i += 1\n",
    "        ptr = ptr.next\n",
    "\n",
    "    if not differ:\n",
    "        return head.next\n",
    "    ptr.next = ptr.next.next\n",
    "    return head\n",
    "\n",
    "\n",
    "def removeNthFromEnd(head, n):\n",
    "    \"\"\"\n",
    "    Using only one pass ie. O(n) and two pointers technique\n",
    "    \"\"\"\n",
    "    slow = head\n",
    "    fast = head\n",
    "\n",
    "    for i in range(n):\n",
    "        fast = fast.next\n",
    "\n",
    "    if fast:  \n",
    "        while fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "        slow.next = slow.next.next\n",
    "    else: \n",
    "        head = head.next #if fast reach upto the end means head node's removal\n",
    "\n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Remove Linked List Elements\n",
    "\n",
    "Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.\n",
    "\n",
    "_Example 1 :_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/06/removelinked-list.jpg\" alt=\"Example1\" width=400 /> <br>\n",
    "Input: head = [1,2,6,3,4,5,6], val = 6 <br>\n",
    "Output: [1,2,3,4,5] <br>\n",
    "\n",
    "_Example 2:_ <br>\n",
    "Input: head = [], val = 1 <br>\n",
    "Output: [] <br>\n",
    "\n",
    "_Example 3:_ <br>\n",
    "Input: head = [7,7,7,7], val = 7 <br>\n",
    "Output: [] <br>\n",
    " \n",
    "_Constraints:_ <br>\n",
    "* The number of nodes in the list is in the range [0, $10^4$].\n",
    "* 1 <= Node.val <= 50\n",
    "* 0 <= val <= 50"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def removeElements(head, val):\n",
    "    \"\"\"\n",
    "    :type head: ListNode\n",
    "    :type val: int\n",
    "    :rtype: ListNode\n",
    "    \"\"\"\n",
    "    # suing two-pointer approach\n",
    "    if not head:\n",
    "        return None\n",
    "\n",
    "    new_head = None     # new_head to be return as a head\n",
    "    ptr = head\n",
    "\n",
    "    while ptr:\n",
    "        if ptr.val != val and not new_head:\n",
    "            new_head = ptr\n",
    "\n",
    "        if ptr.next:\n",
    "            skipper = ptr.next  # this pointer is used for skipping the val\n",
    "            while skipper and skipper.val == val:\n",
    "                skipper = skipper.next    # skips the same val founds\n",
    "            ptr.next = skipper\n",
    "\n",
    "        if ptr:\n",
    "            ptr = ptr.next\n",
    "\n",
    "    return new_head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Odd Even Linked List\n",
    "\n",
    "Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.\n",
    "\n",
    "The *first node* is considered *odd*, and the second node is even, and so on.\n",
    "\n",
    "Note that the relative order inside both the even and odd groups should remain as it was in the input.\n",
    "\n",
    "*You must solve the problem in O(1) extra space complexity and O(n) time complexity.*\n",
    "\n",
    "_Example 1:_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/10/oddeven-linked-list.jpg\" alt=\"example1\" width=300 /> <br>\n",
    "Input: head = [1,2,3,4,5] <br>\n",
    "Output: [1,3,5,2,4] <br>\n",
    "\n",
    "*Example 2:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/10/oddeven2-linked-list.jpg\" alt=\"exaple2\" width=400 /> <br>\n",
    "Input: head = [2,1,3,5,6,4,7] <br>\n",
    "Output: [2,3,6,7,1,5,4] <br>\n",
    " \n",
    "*Constraints:* \n",
    "* n == number of nodes in the linked list\n",
    "* 0 <= n <= $10^4$\n",
    "* $-10^6 <= Node.val <= 10^6 $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def oddEvenList(self, head):\n",
    "    \"\"\"\n",
    "    :type head: ListNode\n",
    "    :rtype: ListNode\n",
    "    Time and space complexity: O(n)\n",
    "    \"\"\"\n",
    "    if not head:\n",
    "        return None\n",
    "\n",
    "    ptr = head\n",
    "    \n",
    "    # creating dummy nodes for odd and even node\n",
    "    dummy_odd = ListNode(0)\n",
    "    odd_tail = dummy_odd\n",
    "\n",
    "    dummy_even = ListNode(0)\n",
    "    even_tail = dummy_even\n",
    "    \n",
    "    # counter to recognize odd or even node\n",
    "    i = 1\n",
    "    while ptr:\n",
    "        if i % 2:\n",
    "            even_tail.next = ptr\n",
    "            even_tail = even_tail.next\n",
    "        else:\n",
    "            odd_tail.next = ptr\n",
    "            odd_tail = odd_tail.next\n",
    "            \n",
    "        ptr = ptr.next\n",
    "        i += 1\n",
    "\n",
    "    # Null or End node is necessary without that cycle found error occurs as End node is not there\n",
    "    even_tail.next = None     \n",
    "\n",
    "    # connecting even node's next (to eliminate 0 we created during dummy node) to the end of odd node\n",
    "    odd_tail.next = dummy_even.next\n",
    "\n",
    "    return dummy_odd.next\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def oddEvenList(self, head):\n",
    "    \"\"\"\n",
    "    :type head: ListNode\n",
    "    :rtype: ListNode\n",
    "    \n",
    "    Time complexity: O(n)\n",
    "    Space complexity: O(1)\n",
    "    \"\"\"\n",
    "    # corner cases\n",
    "    if not head or not head.next or not head.next.next:\n",
    "        return head\n",
    "    \n",
    "    odd_ptr = head\n",
    "    even_ptr = head.next\n",
    "    \n",
    "    # to store the first node of even nodes that will help in connecting to odd_node at-last\n",
    "    even_first = head.next\n",
    "    \n",
    "    while even_ptr and even_ptr.next:\n",
    "        odd_ptr.next = even_ptr.next\n",
    "        odd_ptr = even_ptr.next\n",
    "        \n",
    "        even_ptr.next = odd_ptr.next\n",
    "        even_ptr = odd_ptr.next\n",
    "    \n",
    "    odd_ptr.next = even_first\n",
    "    return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Palindrome Linked List\n",
    "Given the head of a singly linked list, return true if it is a palindrome.\n",
    "\n",
    "_Example 1:_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg\" alt=\"Ex1\" width=400 /> <br>\n",
    "Input: head = [1,2,2,1] <br>\n",
    "Output: true <br>\n",
    "\n",
    "_Example 2:_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg\" alt=\"Ex2\" width=150 /> <br>\n",
    "Input: head = [1,2] <br>\n",
    "Output: false <br>\n",
    " \n",
    "*Constraints:* <br>\n",
    "* The number of nodes in the list is in the range $[1, 10^5]$.\n",
    "* 0 <= Node.val <= 9\n",
    " \n",
    "Follow up: Could you do it in O(n) time and O(1) space?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPalindrome(head):\n",
    "    \"\"\"\n",
    "    :type head: ListNode\n",
    "    :rtype: bool\n",
    "    \n",
    "    Time and space complexity: O(n)\n",
    "    \"\"\"\n",
    "    # corner cases\n",
    "    if not head or not head.next:\n",
    "        return True\n",
    "    \n",
    "    ptr = head\n",
    "    lst1 = list()\n",
    "    \n",
    "    while ptr:\n",
    "        lst1.append(ptr.val)\n",
    "        ptr = ptr.next\n",
    "    \n",
    "    lst2 = lst1[:]\n",
    "    lst2.reverse()\n",
    "    \n",
    "    return lst2 == lst1\n",
    "\n",
    "\n",
    "\n",
    "##########################################################################################################\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution(object):\n",
    "    def reverseList(self, head, upto):\n",
    "        \"\"\"\n",
    "        Auxiliary function to reverse the list upto given nodea and return the current head node \n",
    "        \"\"\"\n",
    "        prev = None\n",
    "        curr = head\n",
    "        nxt = head.next\n",
    "        curr.next = None\n",
    "\n",
    "        while nxt != upto:\n",
    "            prev = curr\n",
    "            curr = nxt\n",
    "            nxt = nxt.next\n",
    "            curr.next = prev\n",
    "\n",
    "        return curr\n",
    "\n",
    "\n",
    "\n",
    "    def frontBackTraverse(self, front_ptr, back_ptr):\n",
    "        \"\"\"\n",
    "        Auxiliary function to check half of the list by traversing right and left at the same time\n",
    "        and return True if node matches\n",
    "        \"\"\"\n",
    "        while front_ptr:\n",
    "            if front_ptr.val != back_ptr.val:\n",
    "                return False\n",
    "            front_ptr = front_ptr.next\n",
    "            back_ptr = back_ptr.next\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "    def isPalindrome(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: bool\n",
    "\n",
    "        Space complexity: O(1)\n",
    "        Time complexity: O(n)\n",
    "        \"\"\"\n",
    "        # corner cases\n",
    "        if not head or not head.next:\n",
    "            return True\n",
    "\n",
    "        ptr = head\n",
    "        mid_pos1 = 0\n",
    "        mid_pos2 = 0    #only required for even size list\n",
    "        even_flag = False\n",
    "        size = 0\n",
    "\n",
    "        while ptr:\n",
    "            size += 1\n",
    "            ptr = ptr.next\n",
    "\n",
    "        if size % 2 == 0:\n",
    "            mid_pos1 = size // 2\n",
    "            mid_pos2 = mid_pos1 + 1\n",
    "            even_flag = True\n",
    "        else:\n",
    "            mid_pos1 = size // 2 + 1\n",
    "\n",
    "        if not even_flag:\n",
    "            i = 1\n",
    "            mid_ptr = head\n",
    "\n",
    "            # traverse the list upto mid_pos\n",
    "            while mid_pos1 != i:\n",
    "                mid_ptr = mid_ptr.next\n",
    "                i += 1\n",
    "\n",
    "            # now reverse the first part beside the mid_ptr\n",
    "            curr = self.reverseList(head, mid_ptr)\n",
    "\n",
    "            # advance the mid_ptr by one as mid pos is same from both the sides\n",
    "            front_ptr = mid_ptr.next\n",
    "            back_ptr = curr\n",
    "\n",
    "            return self.frontBackTraverse(front_ptr, back_ptr)\n",
    "\n",
    "        else:\n",
    "            i = 1\n",
    "            mid_ptr1 = head\n",
    "            mid_ptr2 = None\n",
    "\n",
    "            # traverse upto the mid_pos\n",
    "            while mid_pos1 != i:\n",
    "                mid_ptr1 = mid_ptr1.next\n",
    "                i += 1\n",
    "\n",
    "            mid_ptr2 = mid_ptr1.next\n",
    "\n",
    "            # now reverse the first part beside the mid_ptr2\n",
    "            _ = self.reverseList(head, mid_ptr2)\n",
    "\n",
    "            # now compare the nodes after reversed\n",
    "            front_ptr = mid_ptr2\n",
    "            back_ptr = mid_ptr1\n",
    "\n",
    "            return self.frontBackTraverse(front_ptr, back_ptr)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Design Linked List : Doubly\n",
    "\n",
    "Design your implementation of the linked list. You can choose to use a singly or doubly linked list.<br>\n",
    "A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. <br>\n",
    "If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed. <br>\n",
    "\n",
    "Implement the MyLinkedList class: <br>\n",
    "* _MyLinkedList()_ : Initializes the MyLinkedList object.\n",
    "* _int get(int index)_ : Get the value of the indexth node in the linked list. If the index is invalid, return -1.\n",
    "* _void addAtHead(int val)_ : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.\n",
    "* _void addAtTail(int val)_ : Append a node of value val as the last element of the linked list.\n",
    "* _void addAtIndex(int index, int val)_ : Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.\n",
    "* _void deleteAtIndex(int index)_ : Delete the indexth node in the linked list, if the index is valid.\n",
    " \n",
    "_Example 1:_ <br>\n",
    "Input : <br>\n",
    "`[\"MyLinkedList\", \"addAtHead\", \"addAtTail\", \"addAtIndex\", \"get\", \"deleteAtIndex\", \"get\"]\n",
    "[[], [1], [3], [1, 2], [1], [1], [1]]` <br>\n",
    "Output: <br>\n",
    "`[null, null, null, null, 2, null, 3]` <br>\n",
    "Explanation: <br>\n",
    "MyLinkedList myLinkedList = new MyLinkedList(); <br>\n",
    "myLinkedList.addAtHead(1); <br>\n",
    "myLinkedList.addAtTail(3); <br>\n",
    "myLinkedList.addAtIndex(1, 2);    // linked list becomes 1->2->3 <br>\n",
    "myLinkedList.get(1);              // return 2 <br>\n",
    "myLinkedList.deleteAtIndex(1);    // now the linked list is 1->3 <br>\n",
    "myLinkedList.get(1);              // return 3 <br>\n",
    " \n",
    "_Constraints:_ <br>\n",
    "* 0 <= index, val <= 1000\n",
    "* Please do not use the built-in LinkedList library.\n",
    "* At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.\n",
    "<br>\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.nxt = None\n",
    "        self.pre = None\n",
    "        \n",
    "        \n",
    "class MyLinkedList(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        Initialize your data structure here.\n",
    "        \"\"\"\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "        self.size = 0\n",
    "        \n",
    "\n",
    "    def get(self, index):\n",
    "        \"\"\"\n",
    "        Get the value of the index-th node in the linked list. If the index is invalid, return -1.\n",
    "        :type index: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if index < 0 or index > self.size -1:\n",
    "            return -1\n",
    "        \n",
    "        ptr = self.head\n",
    "        i = 0\n",
    "        \n",
    "        while ptr:\n",
    "            if index == i:\n",
    "                return ptr.val\n",
    "            i += 1\n",
    "            ptr = ptr.nxt\n",
    "            \n",
    "        return -1\n",
    "        \n",
    "\n",
    "    def addAtHead(self, val):\n",
    "        \"\"\"\n",
    "        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.\n",
    "        :type val: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        node = Node(val)\n",
    "        \n",
    "        if not self.head:\n",
    "            self.tail = node\n",
    "        else:\n",
    "            node.nxt = self.head\n",
    "            self.head.pre = node\n",
    "            \n",
    "        self.head = node\n",
    "        self.size += 1\n",
    "            \n",
    "\n",
    "    def addAtTail(self, val):\n",
    "        \"\"\"\n",
    "        Append a node of value val to the last element of the linked list.\n",
    "        :type val: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        node = Node(val)\n",
    "        \n",
    "        if self.tail:\n",
    "            self.tail.nxt = node\n",
    "            node.pre = self.tail\n",
    "        else:\n",
    "            self.head = node\n",
    "            \n",
    "        self.tail = node\n",
    "        self.size += 1\n",
    "        \n",
    "\n",
    "    def addAtIndex(self, index, val):\n",
    "        \"\"\"\n",
    "        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.\n",
    "        :type index: int\n",
    "        :type val: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        if not index:            #if index value is zero\n",
    "            self.addAtHead(val)\n",
    "            return\n",
    "        elif self.size == index:   #if index is equal to lenth of List\n",
    "            self.addAtTail(val)\n",
    "            return\n",
    "        elif self.size < index or index < 0:\n",
    "            return\n",
    "        \n",
    "        i = 0\n",
    "        node = Node(val)\n",
    "        ptr = self.head\n",
    "        \n",
    "        while ptr:\n",
    "            if i == index - 1:\n",
    "                node.nxt = ptr.nxt\n",
    "                ptr.nxt.pre = node\n",
    "                ptr.nxt = node\n",
    "                node.pre = ptr        \n",
    "                break\n",
    "            ptr = ptr.nxt\n",
    "            i += 1\n",
    "            \n",
    "        self.size += 1\n",
    "    \n",
    "\n",
    "    def deleteAtIndex(self, index):\n",
    "        \"\"\"\n",
    "        Delete the index-th node in the linked list, if the index is valid.\n",
    "        :type index: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        if index >= self.size or index < 0:\n",
    "            return\n",
    "            \n",
    "        elif not index:\n",
    "            self.head = self.head.nxt\n",
    "            \n",
    "        elif index == self.size-1:\n",
    "            self.tail = self.tail.pre\n",
    "            \n",
    "        else:\n",
    "            i = 0\n",
    "            ptr = self.head\n",
    "\n",
    "            for i in range(index - 1):\n",
    "                ptr = ptr.nxt\n",
    "\n",
    "            ptr.nxt = ptr.nxt.nxt\n",
    "            ptr.nxt.pre = ptr\n",
    "\n",
    "        self.size -= 1\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "#main\n",
    "obj = MyLinkedList()\n",
    "obj.addAtHead(30)\n",
    "obj.addAtHead(40)\n",
    "obj.addAtIndex(0, 50)\n",
    "obj.addAtIndex(3, 20)\n",
    "obj.addAtTail(10)\n",
    "obj.deleteAtIndex(0)\n",
    "obj.addAtTail(10)\n",
    "obj.deleteAtIndex(4)\n",
    "obj.deleteAtIndex(0)\n",
    "obj.deleteAtIndex(2)\n",
    "obj.addAtTail(10)\n",
    "obj.addAtHead(40)\n",
    "obj.addAtIndex(0, 50)\n",
    "\n",
    "print(\"Length of Linked list is \", obj.size)\n",
    "print(\"Linked List :\", end=\" \")\n",
    "for i in range(obj.size):\n",
    "    print(obj.get(i), \"->\", end=\" \")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Merge Two Sorted Lists\n",
    "\n",
    "Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.\n",
    "\n",
    "*Example 1:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg\" alt=\"example\" width=400 /> <br>\n",
    "Input: l1 = [1,2,4], l2 = [1,3,4] <br>\n",
    "Output: [1,1,2,3,4,4] <br>\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: l1 = [], l2 = [] <br>\n",
    "Output: [] <br>\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: l1 = [], l2 = [0] <br>\n",
    "Output: [0] <br>\n",
    " \n",
    "*Constraints:*\n",
    "* The number of nodes in both lists is in the range [0, 50].\n",
    "* -100 <= Node.val <= 100\n",
    "* Both l1 and l2 are sorted in non-decreasing order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution(object):\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dummyNode = ListNode(0)\n",
    "\n",
    "        tail = dummyNode\n",
    "        while True:\n",
    "\n",
    "            # If any of the list gets completely empty\n",
    "            # directly join all the elements of the other list\n",
    "            if l1 is None:\n",
    "                tail.next = l2\n",
    "                break\n",
    "            if l2 is None:\n",
    "                tail.next = l1\n",
    "                break\n",
    "\n",
    "            # Compare the data of the lists and whichever is smaller is\n",
    "            # appended to the last of the merged list and the head is changed\n",
    "            if l1.val <= l2.val:\n",
    "                tail.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                tail.next = l2\n",
    "                l2 = l2.next\n",
    "        # Advance the tail\n",
    "            tail = tail.next\n",
    "        # Returns the head of the merged list\n",
    "        return dummyNode.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Add Two Numbers\n",
    "You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.\n",
    "\n",
    "You may assume the two numbers do not contain any leading zero, except the number 0 itself.\n",
    "\n",
    "*Example 1:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/10/02/addtwonumber1.jpg\" alt=\"add two num img\" width=400 />\n",
    "<br>\n",
    "Input: l1 = [2,4,3], l2 = [5,6,4] <br>\n",
    "Output: [7,0,8] <br>\n",
    "Explanation: 342 + 465 = 807. <br>\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: l1 = [0], l2 = [0] <br>\n",
    "Output: [0] <br>\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] <br>\n",
    "Output: [8,9,9,9,0,0,0,1] <br>\n",
    " \n",
    "*Constraints:*\n",
    "* The number of nodes in each linked list is in the range [1, 100].\n",
    "* 0 <= Node.val <= 9\n",
    "* It is guaranteed that the list represents a number that does not have leading zeros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution(object):\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        res = ListNode()\n",
    "        tail = res\n",
    "        \n",
    "        ptr1 = l1\n",
    "        ptr2 = l2\n",
    "        add_on = 0\n",
    "        sum_ = 0\n",
    "        \n",
    "        while True:\n",
    "            if not ptr1 and not ptr2:\n",
    "                if add_on:  # if residual left than add to node\n",
    "                    sum_ = 1\n",
    "                else:\n",
    "                    break\n",
    "                    \n",
    "            elif not ptr1:\n",
    "                sum_ = ptr2.val + add_on\n",
    "                ptr2 = ptr2.next\n",
    "                \n",
    "            elif not ptr2:\n",
    "                sum_ = ptr1.val + add_on\n",
    "                ptr1 = ptr1.next\n",
    "                \n",
    "            else :\n",
    "                sum_ = ptr1.val + ptr2.val + add_on\n",
    "                ptr1 = ptr1.next\n",
    "                ptr2 = ptr2.next\n",
    "                \n",
    "            if sum_ >= 10:  \n",
    "                add_on = 1\n",
    "                sum_ -= 10 \n",
    "            else:\n",
    "                add_on = 0\n",
    "\n",
    "            s = ListNode(sum_)\n",
    "            tail.next = s\n",
    "            tail = tail.next\n",
    "            \n",
    "            \n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Flatten a Multilevel Doubly Linked List\n",
    "You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.\n",
    "\n",
    "Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.\n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] <br>\n",
    "Output: [1,2,3,7,8,11,12,9,10,4,5,6] <br>\n",
    "Explanation: The multilevel linked list in the input is as follows:\n",
    "<br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/12/multilevellinkedlist.png\" alt=\"ex1\" />\n",
    "<br>\n",
    "After flattening the multilevel linked list it becomes:\n",
    "<br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2018/10/12/multilevellinkedlistflattened.png\" alt=\"after img\" />\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: head = [1,2,null,3] <br>\n",
    "Output: [1,3,2] <br>\n",
    "Explanation: <br>\n",
    "The input multilevel linked list is as follows: <br>\n",
    "`\n",
    "  1---2---NULL\n",
    "  | \n",
    "  3---NULL \n",
    " `  <br>\n",
    " \n",
    "*Example 3:* <br>\n",
    "Input: head = [] <br>\n",
    "Output: [] <br>\n",
    "\n",
    "How multilevel linked list is represented in test case:<br>\n",
    "\n",
    "We use the multilevel linked list from Example 1 above: <br>\n",
    "`\n",
    " 1---2---3---4---5---6--NULL \n",
    "         |\n",
    "         7---8---9---10--NULL \n",
    "             | \n",
    "             11--12--NULL \n",
    "` <br>\n",
    "\n",
    "The serialization of each level is as follows: <br>\n",
    "[1,2,3,4,5,6,null] <br>\n",
    "[7,8,9,10,null] <br>\n",
    "[11,12,null] <br>\n",
    "To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes: <br>\n",
    "[1,2,3,4,5,6,null] <br>\n",
    "[null,null,7,8,9,10,null] <br>\n",
    "[null,11,12,null] <br>\n",
    "Merging the serialization of each level and removing trailing nulls we obtain: <br>\n",
    "\n",
    "[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] <br>\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* The number of Nodes will not exceed 1000.\n",
    "* 1 <= Node.val <= $10^5$\n",
    "<br>\n",
    "\n",
    "**OMG I made it ! I found recursive solution without any help .... Amazing Gaurav ... Well played**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node(object):\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution(object):\n",
    "    def recursiveTraverse(self, head, lst):\n",
    "        \"\"\"\n",
    "        Auxiliary function to traverse the linked list using recursion.\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return\n",
    "        \n",
    "        elif head.child:\n",
    "            lst.append(head.val)\n",
    "            self.recursiveTraverse(head.child, lst)\n",
    "            self.recursiveTraverse(head.next, lst)\n",
    "            \n",
    "        else:\n",
    "            lst.append(head.val)\n",
    "            self.recursiveTraverse(head.next, lst)\n",
    "\n",
    "            \n",
    "        \n",
    "    def flatten(self, head):\n",
    "        \"\"\"\n",
    "        :type head: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        #corner case\n",
    "        if not head:\n",
    "            return\n",
    "            \n",
    "        lst = list()\n",
    "        ptr = head\n",
    "        \n",
    "        #we are passing list as param, as they're pass by reference\n",
    "        self.recursiveTraverse(head, lst)\n",
    "        \n",
    "        res = Node(lst.pop(0))\n",
    "        tail = res\n",
    "        \n",
    "        while len(lst):\n",
    "            dummy = Node(lst.pop(0))\n",
    "            tail.next = dummy\n",
    "            dummy.prev = tail\n",
    "            tail = tail.next\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Copy List with Random Pointer\n",
    "\n",
    "A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.\n",
    "\n",
    "Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.\n",
    "\n",
    "For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.\n",
    "\n",
    "Return the head of the copied linked list.\n",
    "\n",
    "The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:\n",
    "\n",
    "* val: an integer representing Node.val\n",
    "* random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.\n",
    "\n",
    "Your code will only be given the head of the original linked list.\n",
    "\n",
    "*Example 1:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2019/12/18/e1.png\" alt=\"ex1\" />\n",
    "<br>\n",
    "Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] <br>\n",
    "Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] <br>\n",
    "\n",
    "*Example 2:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2019/12/18/e2.png\" alt=\"ex2\" />\n",
    "<br>\n",
    "Input: head = [[1,1],[2,1]] <br>\n",
    "Output: [[1,1],[2,1]] <br>\n",
    "\n",
    "*Example 3:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2019/12/18/e3.png\" alt=\"ex3\" />\n",
    "<br>\n",
    "Input: head = [[3,null],[3,0],[3,null]] <br>\n",
    "Output: [[3,null],[3,0],[3,null]] <br>\n",
    "\n",
    "*Example 4:* <br>\n",
    "Input: head = [] <br>\n",
    "Output: [] <br>\n",
    "Explanation: The given linked list is empty (null pointer), so return null.\n",
    " \n",
    "*Constraints:*\n",
    "* 0 <= n <= 1000\n",
    "* -10000 <= Node.val <= 10000\n",
    "* Node.random is null or is pointing to some node in the linked list.\n",
    "\n",
    "**Solutions :** <br>\n",
    "* Uses O(n) extra space\n",
    "  1. Create all nodes in copy linked list using next pointers.\n",
    "  2. Store the node and its next pointer mappings of original linked list.\n",
    "  3. Change next pointer of all nodes in original linked list to point to the corresponding node in copy linked list.\n",
    "  4. Change the arbit pointer of all nodes in copy linked list to point to corresponding node in original linked list.\n",
    "  5. Now construct the arbit pointer in copy linked list as below and restore the next pointer of nodes in the original linked list.\n",
    "  \n",
    "            copy_list_node->arbit = copy_list_node->arbit->arbit->next\n",
    "            copy_list_node = copy_list_node->next\n",
    "            \n",
    "  6. Restore the next pointers in original linked list from the stored mappings(in step 2).\n",
    "     \n",
    "            Time Complexity:  O(n) \n",
    "            Auxiliary Space:  O(n) \n",
    "<br>\n",
    "Following diagram shows status of both Linked Lists after above 3 steps. The red arrow shows arbit pointers and black arrow shows next pointers.\n",
    "<img src=\"https://media.geeksforgeeks.org/wp-content/cdn-uploads/2009/08/ArbitLinked-List2.gif\" alt=\"meth1\" />\n",
    "<br>\n",
    "***\n",
    "* Uses `O(1)` extra space\n",
    "  1. Create the copy of node 1 and insert it between node 1 & node 2 in the original Linked List, create a copy of node 2 and insert it between node 2 & 3. Continue in this fashion, add the copy of N after the Nth node \n",
    "  2. Now copy the random link in this fashion \n",
    "         original->next->random= original->random->next;  /*TRAVERSE TWO NODES*/\n",
    "  3. This works because original->next is nothing but a copy of the original and Original->random->next is nothing but a copy of the random. \n",
    "  4. Now restore the original and copy linked lists in this fashion in a single loop. \n",
    "         original->next = original->next->next;\n",
    "         copy->next = copy->next->next;\n",
    "  5. Ensure that original->next is NULL and return the cloned list\n",
    " \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, x, next=None, random=None):\n",
    "        self.val = int(x)\n",
    "        self.next = next\n",
    "        self.random = random\n",
    "\"\"\"\n",
    "\n",
    "class Solution(object):\n",
    "    def copyRandomList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        # Method-1: Using O(n) space\n",
    "        # corner case\n",
    "        if not head:\n",
    "            return \n",
    "        \n",
    "        original = head\n",
    "        copy = Node(0)\n",
    "        original_nxt_mapping = []\n",
    "        \n",
    "        # copy the original list into copy list, except random ptr\n",
    "        tail = copy\n",
    "        while original:\n",
    "            original_nxt_mapping.append(original)\n",
    "            tail.next = Node(original.val)\n",
    "            tail = tail.next\n",
    "            original = original.next\n",
    "        \n",
    "        # to append the null node to last node of original mapping\n",
    "        original_nxt_mapping.append(None)\n",
    "        \n",
    "        # make every node of original node's next to copy node and random ptr of copy to original node\n",
    "        prev = head\n",
    "        curr = head.next\n",
    "        tail = copy.next\n",
    "        \n",
    "        while tail:\n",
    "            prev.next = tail\n",
    "            tail.random = prev\n",
    "            tail = tail.next\n",
    "            prev = curr\n",
    "            \n",
    "            if curr:\n",
    "                curr = curr.next\n",
    "        \n",
    "        # now connect copy's random to original node 's random.next\n",
    "        tail = copy.next\n",
    "        while tail:\n",
    "            if tail.random.random:\n",
    "                tail.random = tail.random.random.next\n",
    "            else:\n",
    "                tail.random = None\n",
    "            tail = tail.next\n",
    "        \n",
    "        # now make the original node as we got ie. fix the node.next part that we have changed \n",
    "        for i in range(len(original_nxt_mapping) - 1):\n",
    "            original_nxt_mapping[i].next = original_nxt_mapping[i+1]\n",
    "            \n",
    "        return copy.next\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rotate List\n",
    "\n",
    "Given the head of a linked list, rotate the list to the right by k places.\n",
    "\n",
    "*Example 1:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/11/13/rotate1.jpg\" alt=\"ex1\" width=400 />\n",
    "<br>\n",
    "Input: head = [1,2,3,4,5], k = 2 <br>\n",
    "Output: [4,5,1,2,3] <br>\n",
    "\n",
    "*Example 2:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/11/13/roate2.jpg\" alt=\"ex2\" width=200 />\n",
    "<br>\n",
    "Input: head = [0,1,2], k = 4 <br>\n",
    "Output: [2,0,1] <br>\n",
    " \n",
    "*Constraints:*\n",
    "* The number of nodes in the list is in the range [0, 500].\n",
    "* -100 <= Node.val <= 100\n",
    "* 0 <= k <= 2 * $10^9$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution(object):\n",
    "    def rotateRight(self, head, k):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type k: int\n",
    "        :rtype: ListNode\n",
    "        \n",
    "        Time Complexity : O(n)\n",
    "        Space Complexity: O(1)\n",
    "        \"\"\"\n",
    "        # corner cases\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        ptr = head\n",
    "        size = 0\n",
    "        \n",
    "        # to find the size of list\n",
    "        while ptr:\n",
    "            size += 1\n",
    "            ptr = ptr.next\n",
    "        \n",
    "        # to find the rotation required after k % size\n",
    "        rot = 0\n",
    "        if k % size == 0:\n",
    "            return head\n",
    "        else:\n",
    "            rot = k % size\n",
    "        \n",
    "        k = rot\n",
    "        prev = head\n",
    "        curr = head.next\n",
    "        tmp_head = None\n",
    "        i = 0\n",
    "        flag = False  \n",
    "        \n",
    "        # now make the (size - k + 1)th node as a tmp_head node and (size -k + 2)th node's next point to null\n",
    "        # and then traverse upto the last node of list and connect the last node.next to the original head\n",
    "        # at last make the tmp_head as permanent head and return the head\n",
    "        while True:\n",
    "            i += 1\n",
    "            if i == (size - k):\n",
    "                prev.next = None\n",
    "                tmp_head = curr\n",
    "                flag = True \n",
    "                \n",
    "            elif flag:\n",
    "                if not curr.next:\n",
    "                    curr.next = head\n",
    "                    head = tmp_head\n",
    "                    break\n",
    "                else:    \n",
    "                    curr = curr.next\n",
    "            \n",
    "            else:\n",
    "                prev = curr\n",
    "                curr = curr.next\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 876. Middle of the Linked List\n",
    "Given the head of a singly linked list, return the middle node of the linked list.\n",
    "\n",
    "If there are two middle nodes, return the second middle node.\n",
    "\n",
    "**Example 1:** <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/07/23/lc-midlist1.jpg\" alt=\"ex1\" width=300 />\n",
    "*Input:* head = [1,2,3,4,5] <br>\n",
    "*Output:* [3,4,5] <br>\n",
    "*Explanation:* The middle node of the list is node 3.\n",
    "\n",
    "\n",
    "**Example 2:**\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/07/23/lc-midlist2.jpg\" alt=\"ex2\" width=300 />\n",
    "*Input:* head = [1,2,3,4,5,6] <br>\n",
    "*Output:* [4,5,6] <br>\n",
    "*Explanation:* Since the list has two middle nodes with values 3 and 4, we return the second one.\n",
    " \n",
    "\n",
    "**Constraints:**\n",
    "* The number of nodes in the list is in the range [1, 100].\n",
    "* 1 <= Node.val <= 100"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def middleNode(self, head):\n",
    "        # By using slow & fast Floyd's approach\n",
    "        slow = fast = head\n",
    "        \n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "        \n",
    "        return slow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 206. Reverse Linked List\n",
    "\n",
    "Given the head of a singly linked list, reverse the list, and return the reversed list.\n",
    "\n",
    "_Example 1:_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg\" alt=\"example 1\" width=500 height=500 /> <br>\n",
    "Input: head = [1,2,3,4,5] <br>\n",
    "Output: [5,4,3,2,1] <br>\n",
    "\n",
    "_Example 2:_ <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg\" alt=\"example 2\" width=150 height=150 /> <br>\n",
    "Input: head = [1,2] <br>\n",
    "Output: [2,1] <br>\n",
    "\n",
    "_Example 3:_ <br>\n",
    "Input: head = [] <br>\n",
    "Output: [] <br>\n",
    " \n",
    "_Constraints:_\n",
    "* The number of nodes in the list is the range [0, 5000].\n",
    "* -5000 <= Node.val <= 5000\n",
    " \n",
    "Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?\n",
    "***\n",
    "**Iterative Solution :**\n",
    "<img src=\"https://media.geeksforgeeks.org/wp-content/cdn-uploads/RGIF2.gif\" alt=\"Iterative Sol\" width=300 />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reverseList(self, head):\n",
    "        prev = None\n",
    "        \n",
    "        while head:\n",
    "            nxtnode = head.next\n",
    "            head.next = prev\n",
    "            prev = head\n",
    "            head = nxtnode\n",
    "        \n",
    "        return prev"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 143. Reorder List\n",
    "You are given the head of a singly linked-list. The list can be represented as:\n",
    "\n",
    "L0 → L1 → … → Ln - 1 → Ln\n",
    "Reorder the list to be on the following form:\n",
    "\n",
    "L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …\n",
    "You may not modify the values in the list's nodes. Only nodes themselves may be changed.\n",
    "\n",
    " \n",
    "\n",
    "**Example 1:**\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg\" alt=\"ex1\" width=300/>\n",
    "*Input:* `head = [1,2,3,4]` <br>\n",
    "*Output:* `[1,4,2,3]`\n",
    "\n",
    "\n",
    "**Example 2:**\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg\" alt=\"ex2\" width=300 />\n",
    "*Input:* `head = [1,2,3,4,5]` <br>\n",
    "*Output:* `[1,5,2,4,3]`\n",
    " \n",
    "\n",
    "**Constraints:**\n",
    "* The number of nodes in the list is in the range [1, 5 * $10^4$].\n",
    "* 1 <= Node.val <= 1000\n",
    "\n",
    "\n",
    "**Solution:**\n",
    "* Solution by partitioning the list (Time & Space complexity: O(n)), it can further be improved by without using additional space and adding the logic from [876. Middle of the Linked List - returns the mid of list using slow-fast pointer approach] and [206. Reverse Linked List - reverses and returns the head of reversed list]\n",
    "\n",
    "<img src=\"background/Reorder Linked List Sol.jpeg\" alt=\"MySolution\" width=500 />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def reorderList(self, head):\n",
    "        \"\"\"\n",
    "        Time complexity : O(n)\n",
    "        Space complexity : O(1)\n",
    "        \"\"\"\n",
    "        def middleNode(head):\n",
    "            # By using slow & fast Floyd's approach\n",
    "            slow = fast = head\n",
    "            while fast and fast.next:\n",
    "                slow = slow.next\n",
    "                fast = fast.next.next\n",
    "            return slow\n",
    "    \n",
    "        def reverseList(head):\n",
    "            prev = None\n",
    "            while head:\n",
    "                nxtnode = head.next\n",
    "                head.next = prev\n",
    "                prev = head\n",
    "                head = nxtnode\n",
    "            return prev\n",
    "        \n",
    "        mid = middleNode(head)\n",
    "        mid.next = reverseList(mid.next)\n",
    "        ptr1, ptr2, ptr3, mid.next = head.next, mid.next, None, None\n",
    "        \n",
    "        while ptr1 and ptr2:\n",
    "            head.next = ptr2\n",
    "            ptr3 = ptr2.next\n",
    "            ptr2.next = ptr1\n",
    "            \n",
    "            head = ptr1 \n",
    "            ptr1 = head.next\n",
    "            ptr2 = ptr3\n",
    "        \n",
    "        \n",
    "    def reorderList2(self, head):\n",
    "        \"\"\"\n",
    "        Do not return anything, modify head in-place instead.\n",
    "        Time and space complexity: O(n)\n",
    "        \"\"\"\n",
    "        # corner-case\n",
    "        if head.next is None: return\n",
    "        ptr = head\n",
    "        node_lst = []\n",
    "        \n",
    "        # Store the nodes in the list\n",
    "        while ptr:\n",
    "            node_lst.append(ptr)\n",
    "            ptr = ptr.next\n",
    "        \n",
    "        partition_len = len(node_lst) // 2\n",
    "        l1 = node_lst[ : partition_len]\n",
    "        l2 = node_lst[partition_len : ]\n",
    "        # Now reverse the l2 and then start merging with l1\n",
    "        l2 = l2[::-1]\n",
    "        ptr = head\n",
    "        nxt = None\n",
    "        \n",
    "        for i in range(partition_len):\n",
    "            nxt = ptr.next\n",
    "            ptr.next = l2[i]\n",
    "            l2[i].next = nxt\n",
    "            ptr = nxt\n",
    "        ptr.next = None\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <font color=\"blue\"> _Tips_ for two pointer technique </font>\n",
    "\n",
    "It is similar to what we have learned in an array. But it can be trickier and error-prone. There are several things we should pay attention:\n",
    "\n",
    "1. Always examine if the node is null before we call the next field.\n",
    "\n",
    "Getting the next node of a null node will cause the null-pointer error. For example, before we run `fast = fast.next.next`, we need to examine both fast and fast.next is not null.\n",
    "\n",
    "2. Carefully define the end conditions of our loop.\n",
    "\n",
    "Run several examples to make sure our end conditions will not result in an endless loop. And we have to take our first tip into consideration when we define our end conditions.\n",
    "\n",
    "_Complexity Analysis :_ <br>\n",
    "It is easy to analyze the space complexity. If we only use pointers without any other extra space, the space complexity will be O(1). However, it is more difficult to analyze the time complexity. In order to get the answer, we need to analyze how many times we will run our loop .\n",
    "\n",
    "In our previous finding cycle example, let's assume that we move the faster pointer 2 steps each time and move the slower pointer 1 step each time.\n",
    "\n",
    "* If there is no cycle, the fast pointer takes N/2 times to reach the end of the linked list, where N is the length of the linked list.\n",
    "* If there is a cycle, the fast pointer needs M times to catch up the slower pointer, where M is the length of the cycle in the list.\n",
    "\n",
    "Obviously, M <= N. So we will run the loop up to N times. And for each loop, we only need constant time. So, the time complexity of this algorithm is O(N) in total."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=\"#FE7401\"> Conclusion </font>\n",
    "Here we provide a comparison of time complexity between the linked list and the array.\n",
    "\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/10/02/comparison_of_time_complexity.png\" alt=\"comaprison img\" >\n",
    "\n",
    "After this comparison, it is not difficult to come up with our conclusion:\n",
    "* If you need to add or delete a node frequently, a linked list could be a good choice.\n",
    "* If you need to access an element by index often, an array might be a better choice than a linked list."
   ]
  }
 ],
 "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}