{"id":"f91dfab0-081b-4005-a1d4-3fd237b586ea","name":"Odd Even Linked List","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of oddEven function. The function is expected to tweak the list such that all odd values are followed by all even values. The relative order of elements should not change. Also, take care of the cases when there are no odd or no even elements. Make sure to properly set head, tail and size as the function will be tested by calling addFirst and addLast.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Time complexity -&gt; O(n)\r\n2. Space complexity -&gt; constant","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <bits/stdc++.h>\n\nusing namespace std;\n\n class Node\n {\n public:\n int data = 0;\n Node *next = nullptr;\n\n Node(int data)\n {\n this->data = data;\n }\n };\n\n\n\nclass linkedlist\n{\n \npublic:\n\n Node *head = nullptr;\n Node *tail = nullptr;\n int size = 0;\n\n //basic->============================================\n\n int size_()\n {\n return this->size;\n }\n\n bool isEmpty()\n {\n return this->size == 0;\n }\n\n string toString()\n {\n Node *curr = this->head;\n string sb = \"\";\n\n while (curr != nullptr)\n {\n sb += to_string(curr->data);\n if (curr->next != nullptr)\n sb += \" \";\n curr = curr->next;\n }\n return sb;\n }\n\n //add->===============================================\nprivate:\n void addFirstNode(Node *node)\n {\n if (this->head == nullptr)\n {\n this->head = node;\n this->tail = node;\n }\n else\n {\n node->next = this->head;\n this->head = node;\n }\n\n this->size++;\n }\n\npublic:\n void addFirst(int val)\n {\n Node *node = new Node(val);\n addFirstNode(node);\n }\n\npublic:\n void addLastNode(Node *node)\n {\n if (this->head == nullptr)\n {\n this->head = node;\n this->tail = node;\n }\n else\n {\n this->tail->next = node;\n this->tail = node;\n }\n\n this->size++;\n }\n\n void addLast(int val)\n {\n Node *node = new Node(val);\n addLastNode(node);\n }\n\n void addNodeAt(Node *node, int idx)\n {\n if (idx == 0)\n addFirstNode(node);\n else if (idx == this->size)\n addLastNode(node);\n else\n {\n Node *prev = getNodeAt(idx - 1);\n Node *curr = prev->next;\n\n prev->next = node;\n curr->next = node;\n\n this->size++;\n }\n }\n\n void addAt(int data, int idx)\n {\n if (idx < 0 || idx > this->size)\n {\n throw(\"invalidLocation: \" + to_string(idx));\n }\n\n Node *node = new Node(data);\n addNodeAt(node, idx);\n }\n\n //remove->============================================\n Node *removeFirstNode()\n {\n Node *node = this->head;\n if (this->size == 1)\n {\n this->head = nullptr;\n this->tail = nullptr;\n }\n else\n {\n this->head = this->head->next;\n node->next = nullptr;\n }\n\n this->size--;\n return node;\n }\n \n void removeFirst()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = removeFirstNode();\n int rv = node->data;\n delete node;\n }\n\n Node *removeLastNode()\n {\n Node *node = this->tail;\n if (this->size == 1)\n {\n this->head = nullptr;\n this->tail = nullptr;\n }\n else\n {\n Node *prev = getNodeAt(this->size - 2);\n this->tail = prev;\n prev->next = nullptr;\n }\n\n this->size--;\n return node;\n }\n\n int removeLast(int val)\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = new Node(val);\n int rv = node->data;\n delete node;\n return rv;\n }\n\n Node *removeNodeAt(int idx)\n {\n if (idx == 0)\n return removeFirstNode();\n else if (idx == this->size - 1)\n return removeLastNode();\n else\n {\n\n Node *prev = getNodeAt(idx - 1);\n Node *curr = prev->next;\n\n prev->next = curr->next;\n curr->next = nullptr;\n\n this->size--;\n return curr;\n }\n }\n\n int removeAt(int idx)\n {\n if (idx < 0 || idx >= this->size)\n {\n throw(\"invalidLocation: \" + idx);\n }\n\n Node *node = removeNodeAt(idx);\n int rv = node->data;\n delete node;\n return rv;\n }\n\n //get->================================================\n Node *getFirstNode()\n {\n return this->head;\n }\n\n int getFirst()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = getFirstNode();\n return node->data;\n }\n\n Node *getLastNode()\n {\n return this->tail;\n }\n\n int getLast()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException\");\n }\n\n Node *node = getLastNode();\n return node->data;\n }\n\n Node *getNodeAt(int idx)\n {\n Node *curr = this->head;\n\n while (idx-- > 0)\n {\n curr = curr->next;\n }\n\n return curr;\n }\n\n int getAt(int idx)\n {\n if (idx < 0 || idx >= this->size)\n {\n throw(\"invalidLocation: \" + idx);\n }\n\n Node *node = getNodeAt(idx);\n return node->data;\n }\n \n \n public:\n void oddEven(){\n //write your code here \n }\n};\n\n \nlinkedlist makeList() {\n linkedlist l;\n int n1;\n cin >> n1;\n\n for (int i = 0; i < n1; i++) {\n int val;\n cin >> val;\n l.addLast(val);\n }\n return l;\n}\n\nint main()\n{\n linkedlist l = makeList();\n int a;\n cin >>a;\n int b;\n cin >>b;\n \n cout<<l.toString()<< endl;\n l.oddEven();\n cout<<l.toString()<< endl;\n l.addLast(b);\n l.addFirst(a);\n cout<<l.toString()<< endl;\n \n return 0;\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 Node f = head;\r\n Node s = head;\r\n\r\n while (f.next != null && f.next.next != null) {\r\n f = f.next.next;\r\n s = s.next;\r\n }\r\n\r\n return s.data;\r\n }\r\n\r\n public static LinkedList mergeTwoSortedLists(LinkedList l1, LinkedList l2) {\r\n LinkedList ml = new LinkedList();\r\n\r\n Node one = l1.head;\r\n Node two = l2.head;\r\n while (one != null && two != null) {\r\n if (one.data < two.data) {\r\n ml.addLast(one.data);\r\n one = one.next;\r\n } else {\r\n ml.addLast(two.data);\r\n two = two.next;\r\n }\r\n }\r\n\r\n while (one != null) {\r\n ml.addLast(one.data);\r\n one = one.next;\r\n }\r\n\r\n while (two != null) {\r\n ml.addLast(two.data);\r\n two = two.next;\r\n }\r\n\r\n return ml;\r\n }\r\n\r\n public static Node midNode(Node head, Node tail){\r\n Node f = head;\r\n Node s = head;\r\n\r\n while(f != tail && f.next != tail){\r\n f = f.next.next;\r\n s = s.next;\r\n }\r\n\r\n return s;\r\n }\r\n\r\n public static LinkedList mergeSort(Node head, Node tail){\r\n if(head == tail){\r\n LinkedList br = new LinkedList();\r\n br.addLast(head.data);\r\n return br;\r\n }\r\n\r\n Node mid = midNode(head, tail);\r\n LinkedList fsh = mergeSort(head, mid);\r\n LinkedList ssh = mergeSort(mid.next, tail);\r\n LinkedList sl = mergeTwoSortedLists(fsh, ssh);\r\n return sl;\r\n }\r\n \r\n public void removeDuplicates(){\r\n LinkedList res = new LinkedList();\r\n\r\n while(this.size() > 0){\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n \r\n if(res.size() == 0 || val != res.tail.data){\r\n res.addLast(val);\r\n }\r\n }\r\n\r\n this.head = res.head;\r\n this.tail = res.tail;\r\n this.size = res.size;\r\n }\r\n \r\n public void oddEven(){\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\r\n int n1 = Integer.parseInt(br.readLine());\r\n LinkedList l1 = new LinkedList();\r\n String[] values1 = br.readLine().split(\" \");\r\n for (int i = 0; i < n1; i++) {\r\n int d = Integer.parseInt(values1[i]);\r\n l1.addLast(d);\r\n }\r\n\r\n int a = Integer.parseInt(br.readLine());\r\n int b = Integer.parseInt(br.readLine());\r\n\r\n l1.display();\r\n l1.oddEven();\r\n l1.display();\r\n l1.addFirst(a);\r\n l1.addLast(b);\r\n l1.display();\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#adding last in linkedlist\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\n self.size += 1\n \n#size of linkedlist\n\n def size(self):\n return self.size\n \n#display a linkedlist\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#remove first\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#get first\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#get last \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#getat in linkedlist\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# add first in linkedlist\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# add at in linkedlist\n\n def addAt(self, idx, val):\n if idx < 0 or idx > size:\n print(\"Invalid arguments\")\n elif idx == 0:\n addFirst(val)\n elif idx == size:\n addLast(val)\n else:\n node = Node()\n node.data = val\n\n temp = 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 size += 1\n\n# remove last in linkedlist\n\n def removeLast(self):\n if size == 0:\n print(\"List is empty\")\n elif size == 1:\n head = tail = None\n size = 0\n else:\n temp = head\n i = 0\n while i < size - 2:\n temp = temp.next\n i += 1\n\n tail = temp\n tail.next = None\n size -= 1\n\n#remove at \n\n def removeAt(self, idx):\n if idx < 0 or idx >= size:\n print(\"Invalid arguments\")\n elif idx == 0:\n removeFirst()\n elif idx == size - 1:\n self.removeLast()\n else:\n temp = head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n\n temp.next = temp.next.next\n size -= 1\n\n# odd even linkedlist\n\n def oddEven(self):\n #write your code here\n \n \n\n# input and output\n\nll = LinkedList()\n\nn = int(input())\nvalues = list(map(int,input().split(\" \")))\nfor i in range(n):\n ll.addLast(values[i])\n \na = int(input())\nb = int(input())\n\nll.display()\nll.oddEven()\nll.display()\nll.addLast(b)\nll.addFirst(a)\nll.display()"}},"points":10,"difficulty":"medium","sampleInput":"7\r\n2 8 9 1 5 4 3\r\n10\r\n100","sampleOutput":"2 8 9 1 5 4 3 \r\n9 1 5 3 2 8 4 \r\n10 9 1 5 3 2 8 4 100","questionVideo":"https://www.youtube.com/embed/58o1--_XGC4","hints":[],"associated":[{"id":"0b53a680-3c59-47eb-add8-ce13d2a42dd3","name":"What will the space complexitty to seprate the ODD-EVEN LinkedList?9Q- OEL)","slug":"what-will-the-space-complexitty-to-seprate-the-odd-even-linkedlist-9q-oel","type":4},{"id":"696c0a83-c1f8-4b15-8980-669551fb6d28","name":"Which of the sorting algorithm is best for LinkedList?(OEl)","slug":"which-of-the-sorting-algorithm-is-best-for-linkedlist-oel","type":4},{"id":"7fc2e559-4852-4730-9852-cc320cbb0b64","name":"Was it mandatory to update the head, tail and size property of the LinkedList at the end?(Q- OEL)","slug":"was-it-mandatory-to-update-the-head-tail-and-size-property-of-the-linkedlist-at-the-end-q-oel","type":4},{"id":"dcd268fa-315e-4467-a5ca-ece99ffe935a","name":"which condition will get execute in the case of No even nodes in the linkedlist(Q- OEL)","slug":"which-condition-will-get-execute-in-the-case-of-no-even-nodes-in-the-linkedlist-q-oel","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":"4feef0bf-7674-4d1c-97ac-8b14f6f38e75","name":"Odd Even Linked List","slug":"odd-even-linked-list","type":1}],"next":{"id":"f44f094e-36f7-453a-9395-c25ff791db29","name":"Odd Even Linked List","type":3,"slug":"odd-even-linked-list"},"prev":{"id":"14b0e902-0f5e-45ad-87e1-477d7d478e52","name":"Remove Duplicates in Sorted Linked List","type":3,"slug":"remove-duplicates-in-sorted-linked-list"}}}

Odd Even Linked List

1. You are given a partially written LinkedList class. 2. You are required to complete the body of oddEven function. The function is expected to tweak the list such that all odd values are followed by all even values. The relative order of elements should not change. Also, take care of the cases when there are no odd or no even elements. Make sure to properly set head, tail and size as the function will be tested by calling addFirst and addLast. 3. Input and Output is managed for you.

{"id":"f91dfab0-081b-4005-a1d4-3fd237b586ea","name":"Odd Even Linked List","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of oddEven function. The function is expected to tweak the list such that all odd values are followed by all even values. The relative order of elements should not change. Also, take care of the cases when there are no odd or no even elements. Make sure to properly set head, tail and size as the function will be tested by calling addFirst and addLast.\r\n3. Input and Output is managed for you.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Time complexity -&gt; O(n)\r\n2. Space complexity -&gt; constant","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <bits/stdc++.h>\n\nusing namespace std;\n\n class Node\n {\n public:\n int data = 0;\n Node *next = nullptr;\n\n Node(int data)\n {\n this->data = data;\n }\n };\n\n\n\nclass linkedlist\n{\n \npublic:\n\n Node *head = nullptr;\n Node *tail = nullptr;\n int size = 0;\n\n //basic->============================================\n\n int size_()\n {\n return this->size;\n }\n\n bool isEmpty()\n {\n return this->size == 0;\n }\n\n string toString()\n {\n Node *curr = this->head;\n string sb = \"\";\n\n while (curr != nullptr)\n {\n sb += to_string(curr->data);\n if (curr->next != nullptr)\n sb += \" \";\n curr = curr->next;\n }\n return sb;\n }\n\n //add->===============================================\nprivate:\n void addFirstNode(Node *node)\n {\n if (this->head == nullptr)\n {\n this->head = node;\n this->tail = node;\n }\n else\n {\n node->next = this->head;\n this->head = node;\n }\n\n this->size++;\n }\n\npublic:\n void addFirst(int val)\n {\n Node *node = new Node(val);\n addFirstNode(node);\n }\n\npublic:\n void addLastNode(Node *node)\n {\n if (this->head == nullptr)\n {\n this->head = node;\n this->tail = node;\n }\n else\n {\n this->tail->next = node;\n this->tail = node;\n }\n\n this->size++;\n }\n\n void addLast(int val)\n {\n Node *node = new Node(val);\n addLastNode(node);\n }\n\n void addNodeAt(Node *node, int idx)\n {\n if (idx == 0)\n addFirstNode(node);\n else if (idx == this->size)\n addLastNode(node);\n else\n {\n Node *prev = getNodeAt(idx - 1);\n Node *curr = prev->next;\n\n prev->next = node;\n curr->next = node;\n\n this->size++;\n }\n }\n\n void addAt(int data, int idx)\n {\n if (idx < 0 || idx > this->size)\n {\n throw(\"invalidLocation: \" + to_string(idx));\n }\n\n Node *node = new Node(data);\n addNodeAt(node, idx);\n }\n\n //remove->============================================\n Node *removeFirstNode()\n {\n Node *node = this->head;\n if (this->size == 1)\n {\n this->head = nullptr;\n this->tail = nullptr;\n }\n else\n {\n this->head = this->head->next;\n node->next = nullptr;\n }\n\n this->size--;\n return node;\n }\n \n void removeFirst()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = removeFirstNode();\n int rv = node->data;\n delete node;\n }\n\n Node *removeLastNode()\n {\n Node *node = this->tail;\n if (this->size == 1)\n {\n this->head = nullptr;\n this->tail = nullptr;\n }\n else\n {\n Node *prev = getNodeAt(this->size - 2);\n this->tail = prev;\n prev->next = nullptr;\n }\n\n this->size--;\n return node;\n }\n\n int removeLast(int val)\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = new Node(val);\n int rv = node->data;\n delete node;\n return rv;\n }\n\n Node *removeNodeAt(int idx)\n {\n if (idx == 0)\n return removeFirstNode();\n else if (idx == this->size - 1)\n return removeLastNode();\n else\n {\n\n Node *prev = getNodeAt(idx - 1);\n Node *curr = prev->next;\n\n prev->next = curr->next;\n curr->next = nullptr;\n\n this->size--;\n return curr;\n }\n }\n\n int removeAt(int idx)\n {\n if (idx < 0 || idx >= this->size)\n {\n throw(\"invalidLocation: \" + idx);\n }\n\n Node *node = removeNodeAt(idx);\n int rv = node->data;\n delete node;\n return rv;\n }\n\n //get->================================================\n Node *getFirstNode()\n {\n return this->head;\n }\n\n int getFirst()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException: -1\");\n }\n\n Node *node = getFirstNode();\n return node->data;\n }\n\n Node *getLastNode()\n {\n return this->tail;\n }\n\n int getLast()\n {\n if (this->size == 0)\n {\n throw(\"nullptrPointerException\");\n }\n\n Node *node = getLastNode();\n return node->data;\n }\n\n Node *getNodeAt(int idx)\n {\n Node *curr = this->head;\n\n while (idx-- > 0)\n {\n curr = curr->next;\n }\n\n return curr;\n }\n\n int getAt(int idx)\n {\n if (idx < 0 || idx >= this->size)\n {\n throw(\"invalidLocation: \" + idx);\n }\n\n Node *node = getNodeAt(idx);\n return node->data;\n }\n \n \n public:\n void oddEven(){\n //write your code here \n }\n};\n\n \nlinkedlist makeList() {\n linkedlist l;\n int n1;\n cin >> n1;\n\n for (int i = 0; i < n1; i++) {\n int val;\n cin >> val;\n l.addLast(val);\n }\n return l;\n}\n\nint main()\n{\n linkedlist l = makeList();\n int a;\n cin >>a;\n int b;\n cin >>b;\n \n cout<<l.toString()<< endl;\n l.oddEven();\n cout<<l.toString()<< endl;\n l.addLast(b);\n l.addFirst(a);\n cout<<l.toString()<< endl;\n \n return 0;\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 Node f = head;\r\n Node s = head;\r\n\r\n while (f.next != null && f.next.next != null) {\r\n f = f.next.next;\r\n s = s.next;\r\n }\r\n\r\n return s.data;\r\n }\r\n\r\n public static LinkedList mergeTwoSortedLists(LinkedList l1, LinkedList l2) {\r\n LinkedList ml = new LinkedList();\r\n\r\n Node one = l1.head;\r\n Node two = l2.head;\r\n while (one != null && two != null) {\r\n if (one.data < two.data) {\r\n ml.addLast(one.data);\r\n one = one.next;\r\n } else {\r\n ml.addLast(two.data);\r\n two = two.next;\r\n }\r\n }\r\n\r\n while (one != null) {\r\n ml.addLast(one.data);\r\n one = one.next;\r\n }\r\n\r\n while (two != null) {\r\n ml.addLast(two.data);\r\n two = two.next;\r\n }\r\n\r\n return ml;\r\n }\r\n\r\n public static Node midNode(Node head, Node tail){\r\n Node f = head;\r\n Node s = head;\r\n\r\n while(f != tail && f.next != tail){\r\n f = f.next.next;\r\n s = s.next;\r\n }\r\n\r\n return s;\r\n }\r\n\r\n public static LinkedList mergeSort(Node head, Node tail){\r\n if(head == tail){\r\n LinkedList br = new LinkedList();\r\n br.addLast(head.data);\r\n return br;\r\n }\r\n\r\n Node mid = midNode(head, tail);\r\n LinkedList fsh = mergeSort(head, mid);\r\n LinkedList ssh = mergeSort(mid.next, tail);\r\n LinkedList sl = mergeTwoSortedLists(fsh, ssh);\r\n return sl;\r\n }\r\n \r\n public void removeDuplicates(){\r\n LinkedList res = new LinkedList();\r\n\r\n while(this.size() > 0){\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n \r\n if(res.size() == 0 || val != res.tail.data){\r\n res.addLast(val);\r\n }\r\n }\r\n\r\n this.head = res.head;\r\n this.tail = res.tail;\r\n this.size = res.size;\r\n }\r\n \r\n public void oddEven(){\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\r\n int n1 = Integer.parseInt(br.readLine());\r\n LinkedList l1 = new LinkedList();\r\n String[] values1 = br.readLine().split(\" \");\r\n for (int i = 0; i < n1; i++) {\r\n int d = Integer.parseInt(values1[i]);\r\n l1.addLast(d);\r\n }\r\n\r\n int a = Integer.parseInt(br.readLine());\r\n int b = Integer.parseInt(br.readLine());\r\n\r\n l1.display();\r\n l1.oddEven();\r\n l1.display();\r\n l1.addFirst(a);\r\n l1.addLast(b);\r\n l1.display();\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#adding last in linkedlist\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\n self.size += 1\n \n#size of linkedlist\n\n def size(self):\n return self.size\n \n#display a linkedlist\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#remove first\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#get first\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#get last \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#getat in linkedlist\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# add first in linkedlist\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# add at in linkedlist\n\n def addAt(self, idx, val):\n if idx < 0 or idx > size:\n print(\"Invalid arguments\")\n elif idx == 0:\n addFirst(val)\n elif idx == size:\n addLast(val)\n else:\n node = Node()\n node.data = val\n\n temp = 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 size += 1\n\n# remove last in linkedlist\n\n def removeLast(self):\n if size == 0:\n print(\"List is empty\")\n elif size == 1:\n head = tail = None\n size = 0\n else:\n temp = head\n i = 0\n while i < size - 2:\n temp = temp.next\n i += 1\n\n tail = temp\n tail.next = None\n size -= 1\n\n#remove at \n\n def removeAt(self, idx):\n if idx < 0 or idx >= size:\n print(\"Invalid arguments\")\n elif idx == 0:\n removeFirst()\n elif idx == size - 1:\n self.removeLast()\n else:\n temp = head\n i = 0\n while i < idx - 1:\n temp = temp.next\n i += 1\n\n temp.next = temp.next.next\n size -= 1\n\n# odd even linkedlist\n\n def oddEven(self):\n #write your code here\n \n \n\n# input and output\n\nll = LinkedList()\n\nn = int(input())\nvalues = list(map(int,input().split(\" \")))\nfor i in range(n):\n ll.addLast(values[i])\n \na = int(input())\nb = int(input())\n\nll.display()\nll.oddEven()\nll.display()\nll.addLast(b)\nll.addFirst(a)\nll.display()"}},"points":10,"difficulty":"medium","sampleInput":"7\r\n2 8 9 1 5 4 3\r\n10\r\n100","sampleOutput":"2 8 9 1 5 4 3 \r\n9 1 5 3 2 8 4 \r\n10 9 1 5 3 2 8 4 100","questionVideo":"https://www.youtube.com/embed/58o1--_XGC4","hints":[],"associated":[{"id":"0b53a680-3c59-47eb-add8-ce13d2a42dd3","name":"What will the space complexitty to seprate the ODD-EVEN LinkedList?9Q- OEL)","slug":"what-will-the-space-complexitty-to-seprate-the-odd-even-linkedlist-9q-oel","type":4},{"id":"696c0a83-c1f8-4b15-8980-669551fb6d28","name":"Which of the sorting algorithm is best for LinkedList?(OEl)","slug":"which-of-the-sorting-algorithm-is-best-for-linkedlist-oel","type":4},{"id":"7fc2e559-4852-4730-9852-cc320cbb0b64","name":"Was it mandatory to update the head, tail and size property of the LinkedList at the end?(Q- OEL)","slug":"was-it-mandatory-to-update-the-head-tail-and-size-property-of-the-linkedlist-at-the-end-q-oel","type":4},{"id":"dcd268fa-315e-4467-a5ca-ece99ffe935a","name":"which condition will get execute in the case of No even nodes in the linkedlist(Q- OEL)","slug":"which-condition-will-get-execute-in-the-case-of-no-even-nodes-in-the-linkedlist-q-oel","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":"4feef0bf-7674-4d1c-97ac-8b14f6f38e75","name":"Odd Even Linked List","slug":"odd-even-linked-list","type":1}],"next":{"id":"f44f094e-36f7-453a-9395-c25ff791db29","name":"Odd Even Linked List","type":3,"slug":"odd-even-linked-list"},"prev":{"id":"14b0e902-0f5e-45ad-87e1-477d7d478e52","name":"Remove Duplicates in Sorted Linked List","type":3,"slug":"remove-duplicates-in-sorted-linked-list"}}}
plane

Editor


Loading...

Odd Even Linked List

medium

1. You are given a partially written LinkedList class. 2. You are required to complete the body of oddEven function. The function is expected to tweak the list such that all odd values are followed by all even values. The relative order of elements should not change. Also, take care of the cases when there are no odd or no even elements. Make sure to properly set head, tail and size as the function will be tested by calling addFirst and addLast. 3. Input and Output is managed for you.

Constraints

1. Time complexity -> O(n) 2. Space complexity -> constant

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

7 2 8 9 1 5 4 3 10 100

Sample Output

2 8 9 1 5 4 3 9 1 5 3 2 8 4 10 9 1 5 3 2 8 4 100

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode