{"id":"37b0d008-bb57-48ba-ba88-733794d058af","name":"Mid Of Linked List","description":"1. You are given a partially written LinkedList class.\r\n2. Here is a list of existing functions:\r\n 2.1 addLast - adds a new element with given value to the end of Linked List\r\n 2.2. display - Prints the elements of linked list from front to end in a single line. \r\n All elements are separated by space\r\n 2.3. size - Returns the number of elements in the linked list.\r\n 2.4. removeFirst - Removes the first element from Linked List. \r\n 2.5. getFirst - Returns the data of first element. \r\n 2.6. getLast - Returns the data of last element. \r\n 2.7. getAt - Returns the data of element available at the index passed. \r\n 2.8. addFirst - adds a new element with given value in front of linked list.\r\n 2.9. addAt - adds a new element at a given index.\r\n 2.10. removeLast - removes the last element of linked list.\r\n 2.11. removeAt - remove an element at a given index\r\n 2.12 kthFromLast - return kth node from end of linked list.\r\n3. You are required to complete the body of mid function. The function should be an iterative function and should return the mid of linked list. Also, make sure to not use size data member directly or indirectly (by calculating size via making a traversal). In linked list of odd size, mid is unambigous. In linked list of even size, consider end of first half as mid.\r\n4. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Size property should not be used directly or indirectly\r\n2. Constant time, single traversal is expected\r\n3. Iterative solution, (not recursion) is expected.","sampleCode":{"cpp":{"code":"#include <iostream>\nusing namespace std;\nclass node{\n public:\n int val;\n node* next;\n \n\n};\nclass LinkedList {\n public: node* head=nullptr;\n node* tail=nullptr;\n int size_=0;\n\nvoid insert_at_tail(int val){\n if(head==NULL){\n node *newnode = new node;\n newnode->val=val;\n newnode->next=NULL;\n head=newnode;\n\n }\n else{\n node *newnode = new node;\n newnode->val=val;\n newnode->next=NULL;\n node *temp = head;\n while(temp->next!=NULL){\n temp=temp->next;\n }\n temp->next = newnode;\n }\n\n}\nvoid insertion_at_head(int val){\n node *newnode = new node;\n newnode->val=val;\n newnode->next=NULL;\n if(head==NULL){\n head=newnode;\n }\n else{\n newnode ->next =head;\n head = newnode;\n }\n\n}\nvoid print (){\n node *temp =head;\n if(head==NULL){\n cout << 0 << endl;\n return;\n }\n while(temp!=NULL){\n cout<<temp->val<<\" \";\n temp=temp->next;\n }\n cout << endl;\n}\nvoid deletion_at_head(){\n if(head==NULL) return;\n node *temp=head;\n head=head->next;\n delete temp;\n\n}\nvoid deletion_at_tail(){\n if(head==NULL) return;\n node* previous=NULL;\n node* temp=head;\n while(temp->next!=NULL){\n previous=temp;\n temp=temp->next;\n }\n previous->next = NULL;\n delete temp; \n}\n\n\nvoid last(){\n node* temp=head;\n while(temp->next!=NULL){\n temp=temp->next;\n }\n cout << temp->val << endl;\n}\nint size(){\n int cnt=0;\n node* temp=head;\n while(temp!=NULL){\n temp=temp->next;\n cnt++;\n }\n return cnt;\n}\nvoid first(){\n cout << head->val << endl;\n}\n\nnode* getAt(int p){\n int cnt=0;\n node* temp=head;\n while(cnt < p){\n cnt++;\n temp=temp->next;\n }\n cout << temp->val << endl;\n return temp;\n}\n\nvoid addAt(int pos,int data){\n if(pos==0){\n insertion_at_head(data);\n return;\n }\n node* newnode=new node;\n newnode->val=data;\n int cnt=0;\n node* temp=head;\n while(cnt<pos-1){\n cnt++;\n temp=temp->next;\n }\n newnode->next=temp->next;\n temp->next=newnode;\n \n}\n\nvoid removeAt(int pos){ \n if(pos==0){\n deletion_at_head();\n return;\n }\n int cnt=0;\n node* temp=head;\n while(cnt<pos-1){\n cnt++;\n temp=temp->next;\n }\n temp->next = temp->next->next;\n}\n\nvoid reverse_di(){\n int left = 0;\n int right = size() - 1;\n while(left < right){\n node* templ = getAt( left);\n node* tempr = getAt( right);\n \n int temp = templ->val;\n templ->val = tempr->val;\n tempr->val = temp;\n left++;\n right--;\n }\n}\nint kthFromEnd(int k){\n if(head==nullptr)\n {\n cout<<\"List is empty\";\n return -1;\n }\n node *temp1=head;\n node *temp2=head;\n for(int i=0;i<k;i++){\n temp2=temp2->next;\n }\n \n while(temp2->next!=nullptr){\n temp2=temp2->next;\n temp1=temp1->next;\n }\n \n return temp1->val;\n}\nvoid mid(){\n // write your code here\n}\n};\nint main() {\n LinkedList l1;\n string s;\n cin >> s;\n while(s!=\"quit\"){\n if(s==\"addLast\"){\n int data;\n cin>> data;\n l1.insert_at_tail(data);\n }\n else if(s==\"addFirst\"){\n int data;\n cin>> data;\n l1.insertion_at_head(data);\n }\n else if(s==\"getFirst\"){\n if(l1.head!=NULL){\n l1.first();\n }else{\n cout << \"List is empty\" << endl;\n }\n }\n else if(s==\"getLast\"){\n if(l1.head!=NULL){\n l1.last();\n } \n else\n {\n cout<<\"List is empty\";\n }\n \n }\n else if(s==\"removeFirst\"){\n if(l1.head!=NULL){\n l1.deletion_at_head();\n }\n else{\n cout << \"List is empty\" << endl; \n }\n }\n else if(s==\"getAt\"){\n if(l1.head!=NULL){\n int i;\n cin >> i; \n if(i>=l1.size()){\n cout << \"Invalid arguments\" << endl;\n }\n else{\n l1.getAt(i);\n }\n }\n else\n {\n cout<<\"List is empty\";\n }\n \n }\n else if(s==\"display\"){\n if(l1.head!=NULL){\n l1.print();\n }\n else{\n cout << endl;\n }\n }\n else if(s==\"size\"){\n if(l1.head!=NULL){\n cout << l1.size() << endl;\n }\n }\n else if(s==\"addAt\"){\n int val,i;\n cin >> i >> val;\n if(i>l1.size()){\n cout << \"Invalid arguments\" << endl;\n }\n else{\n l1.addAt(i,val);\n }\n }\n else if(s == \"removeLast\"){\n if(l1.head!=NULL){\n l1.deletion_at_tail();\n }\n else{\n cout << \"List is empty\" << endl; \n }\n }\n else if(s == \"removeAt\"){\n if(l1.head!=NULL){\n int i;\n cin >> i; \n if(i>l1.size()){\n cout << \"Invalid arguments\" << endl;\n }\n else{\n l1.removeAt(i);\n }\n }\n else{\n cout << \"List is empty\" << endl; \n }\n }else if(s == \"reverseDI\"){\n if(l1.head!=NULL){\n l1.reverse_di();\n }\n else{\n cout << \"List is empty\" << endl; \n }\n }\n else if(s== \"kthFromEnd\"){\n int i;\n cin>>i;\n \n if(i>=l1.size()){\n cout << \"Invalid arguments\" << endl;\n }\n else{\n cout<<l1.kthFromEnd(i)<< endl;\n }\n \n }\n else if(s==\"mid\"){\n l1.mid();\n }\n cin >> s;\n }\n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node next;\r\n }\r\n\r\n public static class LinkedList {\r\n Node head;\r\n Node tail;\r\n int size;\r\n\r\n void addLast(int val) {\r\n Node temp = new Node();\r\n temp.data = val;\r\n temp.next = null;\r\n\r\n if (size == 0) {\r\n head = tail = temp;\r\n } else {\r\n tail.next = temp;\r\n tail = temp;\r\n }\r\n\r\n size++;\r\n }\r\n\r\n public int size() {\r\n return size;\r\n }\r\n\r\n public void display() {\r\n for (Node temp = head; temp != null; temp = temp.next) {\r\n System.out.print(temp.data + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n public void removeFirst() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n } else if (size == 1) {\r\n head = tail = null;\r\n size = 0;\r\n } else {\r\n head = head.next;\r\n size--;\r\n }\r\n }\r\n\r\n public int getFirst() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else {\r\n return head.data;\r\n }\r\n }\r\n\r\n public int getLast() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else {\r\n return tail.data;\r\n }\r\n }\r\n\r\n public int getAt(int idx) {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else if (idx < 0 || idx >= size) {\r\n System.out.println(\"Invalid arguments\");\r\n return -1;\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < idx; i++) {\r\n temp = temp.next;\r\n }\r\n return temp.data;\r\n }\r\n }\r\n\r\n public void addFirst(int val) {\r\n Node temp = new Node();\r\n temp.data = val;\r\n temp.next = head;\r\n head = temp;\r\n\r\n if (size == 0) {\r\n tail = temp;\r\n }\r\n\r\n size++;\r\n }\r\n\r\n public void addAt(int idx, int val) {\r\n if (idx < 0 || idx > size) {\r\n System.out.println(\"Invalid arguments\");\r\n } else if (idx == 0) {\r\n addFirst(val);\r\n } else if (idx == size) {\r\n addLast(val);\r\n } else {\r\n Node node = new Node();\r\n node.data = val;\r\n\r\n Node temp = head;\r\n for (int i = 0; i < idx - 1; i++) {\r\n temp = temp.next;\r\n }\r\n node.next = temp.next;\r\n\r\n temp.next = node;\r\n size++;\r\n }\r\n }\r\n\r\n public void removeLast() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n } else if (size == 1) {\r\n head = tail = null;\r\n size = 0;\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < size - 2; i++) {\r\n temp = temp.next;\r\n }\r\n\r\n tail = temp;\r\n tail.next = null;\r\n size--;\r\n }\r\n }\r\n\r\n public void removeAt(int idx) {\r\n if (idx < 0 || idx >= size) {\r\n System.out.println(\"Invalid arguments\");\r\n } else if (idx == 0) {\r\n removeFirst();\r\n } else if (idx == size - 1) {\r\n removeLast();\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < idx - 1; i++) {\r\n temp = temp.next;\r\n }\r\n\r\n temp.next = temp.next.next;\r\n size--;\r\n }\r\n }\r\n\r\n private Node getNodeAt(int idx) {\r\n Node temp = head;\r\n for (int i = 0; i < idx; i++) {\r\n temp = temp.next;\r\n }\r\n return temp;\r\n }\r\n\r\n public void reverseDI() {\r\n int li = 0;\r\n int ri = size - 1;\r\n while(li < ri){\r\n Node left = getNodeAt(li);\r\n Node right = getNodeAt(ri);\r\n\r\n int temp = left.data;\r\n left.data = right.data;\r\n right.data = temp;\r\n\r\n li++;\r\n ri--;\r\n }\r\n }\r\n \r\n public void reversePI(){\r\n if(size <= 1){\r\n return;\r\n }\r\n\r\n Node prev = null;\r\n Node curr = head;\r\n while(curr != null){\r\n Node next = curr.next;\r\n \r\n curr.next = prev;\r\n prev = curr;\r\n curr = next;\r\n }\r\n\r\n Node temp = head;\r\n head = tail;\r\n tail = temp;\r\n }\r\n \r\n public int kthFromLast(int k){\r\n Node slow = head;\r\n Node fast = head;\r\n for(int i = 0; i < k; i++){\r\n fast = fast.next;\r\n }\r\n\r\n while(fast != tail){\r\n slow = slow.next;\r\n fast = fast.next;\r\n }\r\n\r\n return slow.data;\r\n }\r\n \r\n public int mid(){\r\n // write your code here\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n LinkedList list = new LinkedList();\r\n\r\n String str = br.readLine();\r\n while (str.equals(\"quit\") == false) {\r\n if (str.startsWith(\"addLast\")) {\r\n int val = Integer.parseInt(str.split(\" \")[1]);\r\n list.addLast(val);\r\n } else if (str.startsWith(\"size\")) {\r\n System.out.println(list.size());\r\n } else if (str.startsWith(\"display\")) {\r\n list.display();\r\n } else if (str.startsWith(\"removeFirst\")) {\r\n list.removeFirst();\r\n } else if (str.startsWith(\"getFirst\")) {\r\n int val = list.getFirst();\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"getLast\")) {\r\n int val = list.getLast();\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"getAt\")) {\r\n int idx = Integer.parseInt(str.split(\" \")[1]);\r\n int val = list.getAt(idx);\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"addFirst\")) {\r\n int val = Integer.parseInt(str.split(\" \")[1]);\r\n list.addFirst(val);\r\n } else if (str.startsWith(\"addAt\")) {\r\n int idx = Integer.parseInt(str.split(\" \")[1]);\r\n int val = Integer.parseInt(str.split(\" \")[2]);\r\n list.addAt(idx, val);\r\n } else if (str.startsWith(\"removeLast\")) {\r\n list.removeLast();\r\n } else if (str.startsWith(\"removeAt\")) {\r\n int idx = Integer.parseInt(str.split(\" \")[1]);\r\n list.removeAt(idx);\r\n } else if(str.startsWith(\"reverseDI\")){\r\n list.reverseDI();\r\n } else if(str.startsWith(\"reversePI\")){\r\n list.reversePI();\r\n } else if(str.startsWith(\"kthFromEnd\")){\r\n int idx = Integer.parseInt(str.split(\" \")[1]);\r\n System.out.println(list.kthFromLast(idx));\r\n } else if(str.startsWith(\"mid\")){\r\n System.out.println(list.mid());\r\n }\r\n str = br.readLine();\r\n }\r\n }\r\n}"},"python":{"code":"class Node:\n\n def __init__(self):\n self.data = 0\n self.next = None\n\n\nclass LinkedList:\n\n def __init__(self):\n self.head = None\n self.tail = None\n self.size = 0\n\n def addLast(self, val):\n temp = Node()\n temp.data = val\n temp.next = None\n\n if self.size == 0:\n self.head = self.tail = temp\n else:\n self.tail.next = temp\n self.tail = temp\n self.size += 1\n \n def getNodeAt(self, idx):\n temp = self.head\n i = 0\n while i < idx:\n temp = temp.next\n i += 1\n return temp\n \n def display(self):\n temp = self.head\n while temp is not None:\n print(temp.data, end = \" \")\n temp = temp.next\n print()\n \n def removeFirst(self):\n if self.size == 0:\n print(\"List is empty\")\n elif self.size == 1:\n self.head = self.tail = None\n self.size = 0\n else:\n self.head = self.head.next\n self.size -= 1\n \n def getFirst(self):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n else:\n return self.head.data\n\n def getLast(self):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n else:\n return self.tail.data\n \n def getAt(self, idx):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n elif idx < 0 or idx >= self.size:\n print(\"Invalid arguments\")\n return -1\n else:\n temp = self.head\n i = 0\n while i < idx:\n temp = temp.next\n i += 1\n return temp.data\n \n def addFirst(self, val):\n temp = Node()\n temp.data = val\n temp.next = self.head\n self.head = temp\n\n if self.size == 0:\n self.tail = temp\n\n self.size += 1\n \n def removeAt(self, idx):\n if idx < 0 or idx >= self.size:\n print(\"Invalid arguments\")\n elif idx == 0:\n self.removeFirst()\n elif idx == self.size - 1:\n self.removeLast()\n else:\n temp = self.head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n\n temp.next = temp.next.next\n self.size -= 1\n\n def addAt(self, idx, val):\n if idx < 0 or idx > self.size:\n print(\"Invalid arguments\")\n elif idx == 0:\n self.addFirst(val)\n elif idx == self.size:\n self.addLast(val)\n else:\n node = Node()\n node.data = val\n\n temp = self.head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n node.next = temp.next\n\n temp.next = node\n self.size += 1\n \n def removeLast(self):\n if self.size == 0:\n print(\"List is empty\")\n elif self.size == 1:\n self.head = self.tail = None\n self.size = 0\n else:\n temp = self.head\n i = 0\n while i < self.size - 2:\n temp = temp.next\n i += 1\n\n self.tail = temp\n self.tail.next = None\n self.size -= 1\n \n def reverseDI(self):\n left=0\n right=self.size-1\n while(left<right):\n temp1 = self.getNodeAt(left)\n temp2 = self.getNodeAt(right)\n temp = temp1.data\n temp1.data = temp2.data\n temp2.data = temp\n left+=1\n right-=1\n \n def reversePI(self):\n if self.size <= 1:\n return\n\n prev = None\n curr = self.head\n while curr is not None:\n next = curr.next\n\n curr.next = prev\n prev = curr\n curr = next\n\n temp = self.head\n self.head = self.tail\n self.tail = temp\n \n def kthFromLast(self, k):\n # write your code here\n \nl1 = LinkedList()\nwhile True:\n cmd=input().split(\" \")\n if \"quit\" in cmd[0]:\n break\n elif \"addLast\" in cmd[0]:\n val=int(cmd[1])\n l1.addLast(val)\n elif \"size\" in cmd[0]:\n print(l1.size)\n elif \"display\" in cmd[0]:\n l1.display()\n elif \"removeFirst\" in cmd[0]:\n l1.removeFirst()\n elif \"getFirst\" in cmd[0]:\n ans=l1.getFirst()\n if(ans!=-1):\n print(ans)\n elif \"getLast\" in cmd[0]:\n ans=l1.getLast()\n if(ans!=-1):\n print(ans)\n elif \"getAt\" in cmd[0]:\n idx=int(cmd[1])\n ans=l1.getAt(idx)\n if(ans!=-1):\n print(ans)\n elif \"addFirst\" in cmd[0]:\n val=int(cmd[1])\n l1.addFirst(val)\n elif \"addAt\" in cmd[0]:\n idx=int(cmd[1])\n val=int(cmd[2])\n l1.addAt(idx,val)\n elif \"removeLast\" in cmd[0]:\n l1.removeLast()\n elif \"removeAt\" in cmd[0]:\n idx=int(cmd[1])\n l1.removeAt(idx)\n elif \"reverseDI\" in cmd[0]:\n l1.reverseDI()\n elif \"reversePI\" in cmd[0]:\n l1.reversePI()\n elif \"kthFromEnd\" in cmd[0]:\n idx=int(cmd[1])\n print(l1.kthFromLast(idx));"}},"points":10,"difficulty":"easy","sampleInput":"addLast 10\r\ngetFirst\r\naddLast 20\r\naddLast 30\r\ngetFirst\r\ngetLast\r\ngetAt 1\r\naddLast 40\r\nmid\r\ngetLast\r\naddLast 50\r\nremoveFirst\r\ngetFirst\r\nremoveFirst\r\nremoveFirst\r\nmid\r\nremoveFirst\r\nremoveFirst\r\ngetFirst\r\nquit","sampleOutput":"10\r\n10\r\n30\r\n20\r\n20\r\n40\r\n20\r\n40\r\nList is empty","questionVideo":"https://www.youtube.com/embed/zj94Y_wjAWs","hints":[],"associated":[{"id":"6228cd4d-36ff-4b90-8645-e394998e7d52","name":"Which case is handled by fast.next.next(Q- MDL)","slug":"which-case-is-handled-by-fast-next-next-q-mdl","type":4},{"id":"81c23fca-8576-4a03-b72d-884f6db70634","name":"Count the number of nodes that slow pointer traversed when fast move with the speed 3 times of slow?1 2 3 4 5 6 7 8 9 10 11 13 X(Q- MDL)","slug":"count-the-number-of-nodes-that-slow-pointer-traversed-when-fast-move-with-the-speed-3-times-of-slow-1-2-3-4-5-6-7-8-9-10-11-13-x-q-mdl","type":4},{"id":"d0de548e-9eba-41b2-9178-8785289ebe14","name":"As fast is moving 2 times faster than slow, then what will be the time complexiity(Q- MDL)","slug":"as-fast-is-moving-2-times-faster-than-slow-then-what-will-be-the-time-complexiity-q-mdl","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"91027ef1-2784-45bf-8143-cc6af4560105","name":"Linked Lists For Beginners","slug":"linked-lists-for-beginners","type":0},{"id":"38d99e50-a296-445e-9008-1a8f24dac18d","name":"Mid Of Linked List","slug":"mid-of-linked-list","type":1}],"next":{"id":"b1505a0b-eac5-488d-adad-fb62f41b6098","name":"Mid of Linked List","type":3,"slug":"mid-of-linked-list"},"prev":{"id":"4324aafa-93ed-415f-8978-4320ead4e089","name":"K th Node from End of Linked List","type":3,"slug":"k-th-node-from-end-of-linked-list"}}}

Mid Of Linked List

1. You are given a partially written LinkedList class. 2. Here is a list of existing functions: 2.1 addLast - adds a new element with given value to the end of Linked List 2.2. display - Prints the elements of linked list from front to end in a single line. All elements are separated by space 2.3. size - Returns the number of elements in the linked list. 2.4. removeFirst - Removes the first element from Linked List. 2.5. getFirst - Returns the data of first element. 2.6. getLast - Returns the data of last element. 2.7. getAt - Returns the data of element available at the index passed. 2.8. addFirst - adds a new element with given value in front of linked list. 2.9. addAt - adds a new element at a given index. 2.10. removeLast - removes the last element of linked list. 2.11. removeAt - remove an element at a given index 2.12 kthFromLast - return kth node from end of linked list. 3. You are required to complete the body of mid function. The function should be an iterative function and should return the mid of linked list. Also, make sure to not use size data member directly or indirectly (by calculating size via making a traversal). In linked list of odd size, mid is unambigous. In linked list of even size, consider end of first half as mid. 4. Input and Output is managed for you.

{"id":"37b0d008-bb57-48ba-ba88-733794d058af","name":"Mid Of Linked List","description":"1. You are given a partially written LinkedList class.\r\n2. Here is a list of existing functions:\r\n 2.1 addLast - adds a new element with given value to the end of Linked List\r\n 2.2. display - Prints the elements of linked list from front to end in a single line. \r\n All elements are separated by space\r\n 2.3. size - Returns the number of elements in the linked list.\r\n 2.4. removeFirst - Removes the first element from Linked List. \r\n 2.5. getFirst - Returns the data of first element. \r\n 2.6. getLast - Returns the data of last element. \r\n 2.7. getAt - Returns the data of element available at the index passed. \r\n 2.8. addFirst - adds a new element with given value in front of linked list.\r\n 2.9. addAt - adds a new element at a given index.\r\n 2.10. removeLast - removes the last element of linked list.\r\n 2.11. removeAt - remove an element at a given index\r\n 2.12 kthFromLast - return kth node from end of linked list.\r\n3. You are required to complete the body of mid function. The function should be an iterative function and should return the mid of linked list. Also, make sure to not use size data member directly or indirectly (by calculating size via making a traversal). In linked list of odd size, mid is unambigous. In linked list of even size, consider end of first half as mid.\r\n4. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Size property should not be used directly or indirectly\r\n2. Constant time, single traversal is expected\r\n3. Iterative solution, (not recursion) is expected.","sampleCode":{"cpp":{"code":"#include <iostream>\nusing namespace std;\nclass node{\n public:\n int val;\n node* next;\n \n\n};\nclass LinkedList {\n public: node* head=nullptr;\n node* tail=nullptr;\n int size_=0;\n\nvoid insert_at_tail(int val){\n if(head==NULL){\n node *newnode = new node;\n newnode->val=val;\n newnode->next=NULL;\n head=newnode;\n\n }\n else{\n node *newnode = new node;\n newnode->val=val;\n newnode->next=NULL;\n node *temp = head;\n while(temp->next!=NULL){\n temp=temp->next;\n }\n temp->next = newnode;\n }\n\n}\nvoid insertion_at_head(int val){\n node *newnode = new node;\n newnode->val=val;\n newnode->next=NULL;\n if(head==NULL){\n head=newnode;\n }\n else{\n newnode ->next =head;\n head = newnode;\n }\n\n}\nvoid print (){\n node *temp =head;\n if(head==NULL){\n cout << 0 << endl;\n return;\n }\n while(temp!=NULL){\n cout<<temp->val<<\" \";\n temp=temp->next;\n }\n cout << endl;\n}\nvoid deletion_at_head(){\n if(head==NULL) return;\n node *temp=head;\n head=head->next;\n delete temp;\n\n}\nvoid deletion_at_tail(){\n if(head==NULL) return;\n node* previous=NULL;\n node* temp=head;\n while(temp->next!=NULL){\n previous=temp;\n temp=temp->next;\n }\n previous->next = NULL;\n delete temp; \n}\n\n\nvoid last(){\n node* temp=head;\n while(temp->next!=NULL){\n temp=temp->next;\n }\n cout << temp->val << endl;\n}\nint size(){\n int cnt=0;\n node* temp=head;\n while(temp!=NULL){\n temp=temp->next;\n cnt++;\n }\n return cnt;\n}\nvoid first(){\n cout << head->val << endl;\n}\n\nnode* getAt(int p){\n int cnt=0;\n node* temp=head;\n while(cnt < p){\n cnt++;\n temp=temp->next;\n }\n cout << temp->val << endl;\n return temp;\n}\n\nvoid addAt(int pos,int data){\n if(pos==0){\n insertion_at_head(data);\n return;\n }\n node* newnode=new node;\n newnode->val=data;\n int cnt=0;\n node* temp=head;\n while(cnt<pos-1){\n cnt++;\n temp=temp->next;\n }\n newnode->next=temp->next;\n temp->next=newnode;\n \n}\n\nvoid removeAt(int pos){ \n if(pos==0){\n deletion_at_head();\n return;\n }\n int cnt=0;\n node* temp=head;\n while(cnt<pos-1){\n cnt++;\n temp=temp->next;\n }\n temp->next = temp->next->next;\n}\n\nvoid reverse_di(){\n int left = 0;\n int right = size() - 1;\n while(left < right){\n node* templ = getAt( left);\n node* tempr = getAt( right);\n \n int temp = templ->val;\n templ->val = tempr->val;\n tempr->val = temp;\n left++;\n right--;\n }\n}\nint kthFromEnd(int k){\n if(head==nullptr)\n {\n cout<<\"List is empty\";\n return -1;\n }\n node *temp1=head;\n node *temp2=head;\n for(int i=0;i<k;i++){\n temp2=temp2->next;\n }\n \n while(temp2->next!=nullptr){\n temp2=temp2->next;\n temp1=temp1->next;\n }\n \n return temp1->val;\n}\nvoid mid(){\n // write your code here\n}\n};\nint main() {\n LinkedList l1;\n string s;\n cin >> s;\n while(s!=\"quit\"){\n if(s==\"addLast\"){\n int data;\n cin>> data;\n l1.insert_at_tail(data);\n }\n else if(s==\"addFirst\"){\n int data;\n cin>> data;\n l1.insertion_at_head(data);\n }\n else if(s==\"getFirst\"){\n if(l1.head!=NULL){\n l1.first();\n }else{\n cout << \"List is empty\" << endl;\n }\n }\n else if(s==\"getLast\"){\n if(l1.head!=NULL){\n l1.last();\n } \n else\n {\n cout<<\"List is empty\";\n }\n \n }\n else if(s==\"removeFirst\"){\n if(l1.head!=NULL){\n l1.deletion_at_head();\n }\n else{\n cout << \"List is empty\" << endl; \n }\n }\n else if(s==\"getAt\"){\n if(l1.head!=NULL){\n int i;\n cin >> i; \n if(i>=l1.size()){\n cout << \"Invalid arguments\" << endl;\n }\n else{\n l1.getAt(i);\n }\n }\n else\n {\n cout<<\"List is empty\";\n }\n \n }\n else if(s==\"display\"){\n if(l1.head!=NULL){\n l1.print();\n }\n else{\n cout << endl;\n }\n }\n else if(s==\"size\"){\n if(l1.head!=NULL){\n cout << l1.size() << endl;\n }\n }\n else if(s==\"addAt\"){\n int val,i;\n cin >> i >> val;\n if(i>l1.size()){\n cout << \"Invalid arguments\" << endl;\n }\n else{\n l1.addAt(i,val);\n }\n }\n else if(s == \"removeLast\"){\n if(l1.head!=NULL){\n l1.deletion_at_tail();\n }\n else{\n cout << \"List is empty\" << endl; \n }\n }\n else if(s == \"removeAt\"){\n if(l1.head!=NULL){\n int i;\n cin >> i; \n if(i>l1.size()){\n cout << \"Invalid arguments\" << endl;\n }\n else{\n l1.removeAt(i);\n }\n }\n else{\n cout << \"List is empty\" << endl; \n }\n }else if(s == \"reverseDI\"){\n if(l1.head!=NULL){\n l1.reverse_di();\n }\n else{\n cout << \"List is empty\" << endl; \n }\n }\n else if(s== \"kthFromEnd\"){\n int i;\n cin>>i;\n \n if(i>=l1.size()){\n cout << \"Invalid arguments\" << endl;\n }\n else{\n cout<<l1.kthFromEnd(i)<< endl;\n }\n \n }\n else if(s==\"mid\"){\n l1.mid();\n }\n cin >> s;\n }\n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node next;\r\n }\r\n\r\n public static class LinkedList {\r\n Node head;\r\n Node tail;\r\n int size;\r\n\r\n void addLast(int val) {\r\n Node temp = new Node();\r\n temp.data = val;\r\n temp.next = null;\r\n\r\n if (size == 0) {\r\n head = tail = temp;\r\n } else {\r\n tail.next = temp;\r\n tail = temp;\r\n }\r\n\r\n size++;\r\n }\r\n\r\n public int size() {\r\n return size;\r\n }\r\n\r\n public void display() {\r\n for (Node temp = head; temp != null; temp = temp.next) {\r\n System.out.print(temp.data + \" \");\r\n }\r\n System.out.println();\r\n }\r\n\r\n public void removeFirst() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n } else if (size == 1) {\r\n head = tail = null;\r\n size = 0;\r\n } else {\r\n head = head.next;\r\n size--;\r\n }\r\n }\r\n\r\n public int getFirst() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else {\r\n return head.data;\r\n }\r\n }\r\n\r\n public int getLast() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else {\r\n return tail.data;\r\n }\r\n }\r\n\r\n public int getAt(int idx) {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n return -1;\r\n } else if (idx < 0 || idx >= size) {\r\n System.out.println(\"Invalid arguments\");\r\n return -1;\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < idx; i++) {\r\n temp = temp.next;\r\n }\r\n return temp.data;\r\n }\r\n }\r\n\r\n public void addFirst(int val) {\r\n Node temp = new Node();\r\n temp.data = val;\r\n temp.next = head;\r\n head = temp;\r\n\r\n if (size == 0) {\r\n tail = temp;\r\n }\r\n\r\n size++;\r\n }\r\n\r\n public void addAt(int idx, int val) {\r\n if (idx < 0 || idx > size) {\r\n System.out.println(\"Invalid arguments\");\r\n } else if (idx == 0) {\r\n addFirst(val);\r\n } else if (idx == size) {\r\n addLast(val);\r\n } else {\r\n Node node = new Node();\r\n node.data = val;\r\n\r\n Node temp = head;\r\n for (int i = 0; i < idx - 1; i++) {\r\n temp = temp.next;\r\n }\r\n node.next = temp.next;\r\n\r\n temp.next = node;\r\n size++;\r\n }\r\n }\r\n\r\n public void removeLast() {\r\n if (size == 0) {\r\n System.out.println(\"List is empty\");\r\n } else if (size == 1) {\r\n head = tail = null;\r\n size = 0;\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < size - 2; i++) {\r\n temp = temp.next;\r\n }\r\n\r\n tail = temp;\r\n tail.next = null;\r\n size--;\r\n }\r\n }\r\n\r\n public void removeAt(int idx) {\r\n if (idx < 0 || idx >= size) {\r\n System.out.println(\"Invalid arguments\");\r\n } else if (idx == 0) {\r\n removeFirst();\r\n } else if (idx == size - 1) {\r\n removeLast();\r\n } else {\r\n Node temp = head;\r\n for (int i = 0; i < idx - 1; i++) {\r\n temp = temp.next;\r\n }\r\n\r\n temp.next = temp.next.next;\r\n size--;\r\n }\r\n }\r\n\r\n private Node getNodeAt(int idx) {\r\n Node temp = head;\r\n for (int i = 0; i < idx; i++) {\r\n temp = temp.next;\r\n }\r\n return temp;\r\n }\r\n\r\n public void reverseDI() {\r\n int li = 0;\r\n int ri = size - 1;\r\n while(li < ri){\r\n Node left = getNodeAt(li);\r\n Node right = getNodeAt(ri);\r\n\r\n int temp = left.data;\r\n left.data = right.data;\r\n right.data = temp;\r\n\r\n li++;\r\n ri--;\r\n }\r\n }\r\n \r\n public void reversePI(){\r\n if(size <= 1){\r\n return;\r\n }\r\n\r\n Node prev = null;\r\n Node curr = head;\r\n while(curr != null){\r\n Node next = curr.next;\r\n \r\n curr.next = prev;\r\n prev = curr;\r\n curr = next;\r\n }\r\n\r\n Node temp = head;\r\n head = tail;\r\n tail = temp;\r\n }\r\n \r\n public int kthFromLast(int k){\r\n Node slow = head;\r\n Node fast = head;\r\n for(int i = 0; i < k; i++){\r\n fast = fast.next;\r\n }\r\n\r\n while(fast != tail){\r\n slow = slow.next;\r\n fast = fast.next;\r\n }\r\n\r\n return slow.data;\r\n }\r\n \r\n public int mid(){\r\n // write your code here\r\n }\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n LinkedList list = new LinkedList();\r\n\r\n String str = br.readLine();\r\n while (str.equals(\"quit\") == false) {\r\n if (str.startsWith(\"addLast\")) {\r\n int val = Integer.parseInt(str.split(\" \")[1]);\r\n list.addLast(val);\r\n } else if (str.startsWith(\"size\")) {\r\n System.out.println(list.size());\r\n } else if (str.startsWith(\"display\")) {\r\n list.display();\r\n } else if (str.startsWith(\"removeFirst\")) {\r\n list.removeFirst();\r\n } else if (str.startsWith(\"getFirst\")) {\r\n int val = list.getFirst();\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"getLast\")) {\r\n int val = list.getLast();\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"getAt\")) {\r\n int idx = Integer.parseInt(str.split(\" \")[1]);\r\n int val = list.getAt(idx);\r\n if (val != -1) {\r\n System.out.println(val);\r\n }\r\n } else if (str.startsWith(\"addFirst\")) {\r\n int val = Integer.parseInt(str.split(\" \")[1]);\r\n list.addFirst(val);\r\n } else if (str.startsWith(\"addAt\")) {\r\n int idx = Integer.parseInt(str.split(\" \")[1]);\r\n int val = Integer.parseInt(str.split(\" \")[2]);\r\n list.addAt(idx, val);\r\n } else if (str.startsWith(\"removeLast\")) {\r\n list.removeLast();\r\n } else if (str.startsWith(\"removeAt\")) {\r\n int idx = Integer.parseInt(str.split(\" \")[1]);\r\n list.removeAt(idx);\r\n } else if(str.startsWith(\"reverseDI\")){\r\n list.reverseDI();\r\n } else if(str.startsWith(\"reversePI\")){\r\n list.reversePI();\r\n } else if(str.startsWith(\"kthFromEnd\")){\r\n int idx = Integer.parseInt(str.split(\" \")[1]);\r\n System.out.println(list.kthFromLast(idx));\r\n } else if(str.startsWith(\"mid\")){\r\n System.out.println(list.mid());\r\n }\r\n str = br.readLine();\r\n }\r\n }\r\n}"},"python":{"code":"class Node:\n\n def __init__(self):\n self.data = 0\n self.next = None\n\n\nclass LinkedList:\n\n def __init__(self):\n self.head = None\n self.tail = None\n self.size = 0\n\n def addLast(self, val):\n temp = Node()\n temp.data = val\n temp.next = None\n\n if self.size == 0:\n self.head = self.tail = temp\n else:\n self.tail.next = temp\n self.tail = temp\n self.size += 1\n \n def getNodeAt(self, idx):\n temp = self.head\n i = 0\n while i < idx:\n temp = temp.next\n i += 1\n return temp\n \n def display(self):\n temp = self.head\n while temp is not None:\n print(temp.data, end = \" \")\n temp = temp.next\n print()\n \n def removeFirst(self):\n if self.size == 0:\n print(\"List is empty\")\n elif self.size == 1:\n self.head = self.tail = None\n self.size = 0\n else:\n self.head = self.head.next\n self.size -= 1\n \n def getFirst(self):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n else:\n return self.head.data\n\n def getLast(self):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n else:\n return self.tail.data\n \n def getAt(self, idx):\n if self.size == 0:\n print(\"List is empty\")\n return -1\n elif idx < 0 or idx >= self.size:\n print(\"Invalid arguments\")\n return -1\n else:\n temp = self.head\n i = 0\n while i < idx:\n temp = temp.next\n i += 1\n return temp.data\n \n def addFirst(self, val):\n temp = Node()\n temp.data = val\n temp.next = self.head\n self.head = temp\n\n if self.size == 0:\n self.tail = temp\n\n self.size += 1\n \n def removeAt(self, idx):\n if idx < 0 or idx >= self.size:\n print(\"Invalid arguments\")\n elif idx == 0:\n self.removeFirst()\n elif idx == self.size - 1:\n self.removeLast()\n else:\n temp = self.head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n\n temp.next = temp.next.next\n self.size -= 1\n\n def addAt(self, idx, val):\n if idx < 0 or idx > self.size:\n print(\"Invalid arguments\")\n elif idx == 0:\n self.addFirst(val)\n elif idx == self.size:\n self.addLast(val)\n else:\n node = Node()\n node.data = val\n\n temp = self.head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n node.next = temp.next\n\n temp.next = node\n self.size += 1\n \n def removeLast(self):\n if self.size == 0:\n print(\"List is empty\")\n elif self.size == 1:\n self.head = self.tail = None\n self.size = 0\n else:\n temp = self.head\n i = 0\n while i < self.size - 2:\n temp = temp.next\n i += 1\n\n self.tail = temp\n self.tail.next = None\n self.size -= 1\n \n def reverseDI(self):\n left=0\n right=self.size-1\n while(left<right):\n temp1 = self.getNodeAt(left)\n temp2 = self.getNodeAt(right)\n temp = temp1.data\n temp1.data = temp2.data\n temp2.data = temp\n left+=1\n right-=1\n \n def reversePI(self):\n if self.size <= 1:\n return\n\n prev = None\n curr = self.head\n while curr is not None:\n next = curr.next\n\n curr.next = prev\n prev = curr\n curr = next\n\n temp = self.head\n self.head = self.tail\n self.tail = temp\n \n def kthFromLast(self, k):\n # write your code here\n \nl1 = LinkedList()\nwhile True:\n cmd=input().split(\" \")\n if \"quit\" in cmd[0]:\n break\n elif \"addLast\" in cmd[0]:\n val=int(cmd[1])\n l1.addLast(val)\n elif \"size\" in cmd[0]:\n print(l1.size)\n elif \"display\" in cmd[0]:\n l1.display()\n elif \"removeFirst\" in cmd[0]:\n l1.removeFirst()\n elif \"getFirst\" in cmd[0]:\n ans=l1.getFirst()\n if(ans!=-1):\n print(ans)\n elif \"getLast\" in cmd[0]:\n ans=l1.getLast()\n if(ans!=-1):\n print(ans)\n elif \"getAt\" in cmd[0]:\n idx=int(cmd[1])\n ans=l1.getAt(idx)\n if(ans!=-1):\n print(ans)\n elif \"addFirst\" in cmd[0]:\n val=int(cmd[1])\n l1.addFirst(val)\n elif \"addAt\" in cmd[0]:\n idx=int(cmd[1])\n val=int(cmd[2])\n l1.addAt(idx,val)\n elif \"removeLast\" in cmd[0]:\n l1.removeLast()\n elif \"removeAt\" in cmd[0]:\n idx=int(cmd[1])\n l1.removeAt(idx)\n elif \"reverseDI\" in cmd[0]:\n l1.reverseDI()\n elif \"reversePI\" in cmd[0]:\n l1.reversePI()\n elif \"kthFromEnd\" in cmd[0]:\n idx=int(cmd[1])\n print(l1.kthFromLast(idx));"}},"points":10,"difficulty":"easy","sampleInput":"addLast 10\r\ngetFirst\r\naddLast 20\r\naddLast 30\r\ngetFirst\r\ngetLast\r\ngetAt 1\r\naddLast 40\r\nmid\r\ngetLast\r\naddLast 50\r\nremoveFirst\r\ngetFirst\r\nremoveFirst\r\nremoveFirst\r\nmid\r\nremoveFirst\r\nremoveFirst\r\ngetFirst\r\nquit","sampleOutput":"10\r\n10\r\n30\r\n20\r\n20\r\n40\r\n20\r\n40\r\nList is empty","questionVideo":"https://www.youtube.com/embed/zj94Y_wjAWs","hints":[],"associated":[{"id":"6228cd4d-36ff-4b90-8645-e394998e7d52","name":"Which case is handled by fast.next.next(Q- MDL)","slug":"which-case-is-handled-by-fast-next-next-q-mdl","type":4},{"id":"81c23fca-8576-4a03-b72d-884f6db70634","name":"Count the number of nodes that slow pointer traversed when fast move with the speed 3 times of slow?1 2 3 4 5 6 7 8 9 10 11 13 X(Q- MDL)","slug":"count-the-number-of-nodes-that-slow-pointer-traversed-when-fast-move-with-the-speed-3-times-of-slow-1-2-3-4-5-6-7-8-9-10-11-13-x-q-mdl","type":4},{"id":"d0de548e-9eba-41b2-9178-8785289ebe14","name":"As fast is moving 2 times faster than slow, then what will be the time complexiity(Q- MDL)","slug":"as-fast-is-moving-2-times-faster-than-slow-then-what-will-be-the-time-complexiity-q-mdl","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"91027ef1-2784-45bf-8143-cc6af4560105","name":"Linked Lists For Beginners","slug":"linked-lists-for-beginners","type":0},{"id":"38d99e50-a296-445e-9008-1a8f24dac18d","name":"Mid Of Linked List","slug":"mid-of-linked-list","type":1}],"next":{"id":"b1505a0b-eac5-488d-adad-fb62f41b6098","name":"Mid of Linked List","type":3,"slug":"mid-of-linked-list"},"prev":{"id":"4324aafa-93ed-415f-8978-4320ead4e089","name":"K th Node from End of Linked List","type":3,"slug":"k-th-node-from-end-of-linked-list"}}}
plane

Editor

Loading...

Mid Of Linked List

easy

1. You are given a partially written LinkedList class. 2. Here is a list of existing functions: 2.1 addLast - adds a new element with given value to the end of Linked List 2.2. display - Prints the elements of linked list from front to end in a single line. All elements are separated by space 2.3. size - Returns the number of elements in the linked list. 2.4. removeFirst - Removes the first element from Linked List. 2.5. getFirst - Returns the data of first element. 2.6. getLast - Returns the data of last element. 2.7. getAt - Returns the data of element available at the index passed. 2.8. addFirst - adds a new element with given value in front of linked list. 2.9. addAt - adds a new element at a given index. 2.10. removeLast - removes the last element of linked list. 2.11. removeAt - remove an element at a given index 2.12 kthFromLast - return kth node from end of linked list. 3. You are required to complete the body of mid function. The function should be an iterative function and should return the mid of linked list. Also, make sure to not use size data member directly or indirectly (by calculating size via making a traversal). In linked list of odd size, mid is unambigous. In linked list of even size, consider end of first half as mid. 4. Input and Output is managed for you.

Constraints

1. Size property should not be used directly or indirectly 2. Constant time, single traversal is expected 3. Iterative solution, (not recursion) is expected.

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

addLast 10 getFirst addLast 20 addLast 30 getFirst getLast getAt 1 addLast 40 mid getLast addLast 50 removeFirst getFirst removeFirst removeFirst mid removeFirst removeFirst getFirst quit

Sample Output

10 10 30 20 20 40 20 40 List is empty

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode