{"id":"c465bd48-24fc-4f9e-9e44-f7cfa570f406","name":"K Reverse In Linked List","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of kReverse function. The function is expected to tweak the list such that all groups of k elements in the list get reversed and linked. If the last set has less than k elements, leave it as it is (don't reverse).\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 int removeFirst(int val)\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 return rv;\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 kReverse(int k){\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 k;\n cin >>k;\n int a;\n cin >>a;\n int b;\n cin >>b;\n \n cout<<l.toString()<< endl;\n l.kReverse(k);\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 LinkedList odd = new LinkedList();\r\n LinkedList even = 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 (val % 2 == 0) {\r\n even.addLast(val);\r\n } else {\r\n odd.addLast(val);\r\n }\r\n }\r\n\r\n if (odd.size > 0 && even.size > 0) {\r\n odd.tail.next = even.head;\r\n\r\n this.head = odd.head;\r\n this.tail = even.tail;\r\n this.size = odd.size + even.size;\r\n } else if (odd.size > 0) {\r\n this.head = odd.head;\r\n this.tail = odd.tail;\r\n this.size = odd.size;\r\n } else if (even.size > 0) {\r\n this.head = even.head;\r\n this.tail = even.tail;\r\n this.size = even.size;\r\n }\r\n }\r\n\r\n public void kReverse(int k) {\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 k = Integer.parseInt(br.readLine());\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.kReverse(k);\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# k reverese\n\n def kReverse(self, k):\n #write your code here\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 \nk =int( input())\na = int(input())\nb = int(input())\n\nll.display()\nll.kReverse(k)\nll.display()\nll.addFirst(a)\nll.addLast(b)\nll.display()"}},"points":10,"difficulty":"easy","sampleInput":"11\r\n1 2 3 4 5 6 7 8 9 10 11\r\n3\r\n100\r\n200","sampleOutput":"1 2 3 4 5 6 7 8 9 10 11 \r\n3 2 1 6 5 4 9 8 7 10 11 \r\n100 3 2 1 6 5 4 9 8 7 10 11 200","questionVideo":"https://www.youtube.com/embed/Ko3DktYG4zs","hints":[],"associated":[{"id":"5f9a279d-d3c9-428a-8b1f-0740304a486a","name":"What is the time complexity of K reverse in a linked list?(Q- KRL)","slug":"what-is-the-time-complexity-of-k-reverse-in-a-linked-list-q-krl","type":4},{"id":"6c37d751-e473-45a6-ad30-c0fe4528d8b4","name":"In K reverse problem, if the last set has less than k elements, what will you do?(KRL)","slug":"in-k-reverse-problem-if-the-last-set-has-less-than-k-elements-what-will-you-do-krl","type":4},{"id":"80fc653c-64cb-464a-96b1-071e97b48a32","name":"What is the space complexity of K reverse in a linked list?(Q- KRL)","slug":"what-is-the-space-complexity-of-k-reverse-in-a-linked-list-q-krl","type":4},{"id":"ba618aad-140d-4d07-875e-01fc547d7b28","name":"If the size of the linked list is greater than the value of k, how will you add the elements in the new list?(Q- KRL)","slug":"if-the-size-of-the-linked-list-is-greater-than-the-value-of-k-how-will-you-add-the-elements-in-the-new-list-q-krl","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":"d2da6b99-4588-4cb8-8ff2-a897b6126768","name":"K Reverse In Linked List","slug":"k-reverse-in-linked-list","type":1}],"next":{"id":"ab9832c9-f9a2-412d-b490-450cdbccae79","name":"K Reverse In Linked List","type":3,"slug":"k-reverse-in-linked-list"},"prev":{"id":"f44f094e-36f7-453a-9395-c25ff791db29","name":"Odd Even Linked List","type":3,"slug":"odd-even-linked-list"}}}

K Reverse In Linked List

1. You are given a partially written LinkedList class. 2. You are required to complete the body of kReverse function. The function is expected to tweak the list such that all groups of k elements in the list get reversed and linked. If the last set has less than k elements, leave it as it is (don't reverse). 3. Input and Output is managed for you.

{"id":"c465bd48-24fc-4f9e-9e44-f7cfa570f406","name":"K Reverse In Linked List","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of kReverse function. The function is expected to tweak the list such that all groups of k elements in the list get reversed and linked. If the last set has less than k elements, leave it as it is (don't reverse).\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 int removeFirst(int val)\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 return rv;\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 kReverse(int k){\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 k;\n cin >>k;\n int a;\n cin >>a;\n int b;\n cin >>b;\n \n cout<<l.toString()<< endl;\n l.kReverse(k);\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 LinkedList odd = new LinkedList();\r\n LinkedList even = 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 (val % 2 == 0) {\r\n even.addLast(val);\r\n } else {\r\n odd.addLast(val);\r\n }\r\n }\r\n\r\n if (odd.size > 0 && even.size > 0) {\r\n odd.tail.next = even.head;\r\n\r\n this.head = odd.head;\r\n this.tail = even.tail;\r\n this.size = odd.size + even.size;\r\n } else if (odd.size > 0) {\r\n this.head = odd.head;\r\n this.tail = odd.tail;\r\n this.size = odd.size;\r\n } else if (even.size > 0) {\r\n this.head = even.head;\r\n this.tail = even.tail;\r\n this.size = even.size;\r\n }\r\n }\r\n\r\n public void kReverse(int k) {\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 k = Integer.parseInt(br.readLine());\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.kReverse(k);\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# k reverese\n\n def kReverse(self, k):\n #write your code here\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 \nk =int( input())\na = int(input())\nb = int(input())\n\nll.display()\nll.kReverse(k)\nll.display()\nll.addFirst(a)\nll.addLast(b)\nll.display()"}},"points":10,"difficulty":"easy","sampleInput":"11\r\n1 2 3 4 5 6 7 8 9 10 11\r\n3\r\n100\r\n200","sampleOutput":"1 2 3 4 5 6 7 8 9 10 11 \r\n3 2 1 6 5 4 9 8 7 10 11 \r\n100 3 2 1 6 5 4 9 8 7 10 11 200","questionVideo":"https://www.youtube.com/embed/Ko3DktYG4zs","hints":[],"associated":[{"id":"5f9a279d-d3c9-428a-8b1f-0740304a486a","name":"What is the time complexity of K reverse in a linked list?(Q- KRL)","slug":"what-is-the-time-complexity-of-k-reverse-in-a-linked-list-q-krl","type":4},{"id":"6c37d751-e473-45a6-ad30-c0fe4528d8b4","name":"In K reverse problem, if the last set has less than k elements, what will you do?(KRL)","slug":"in-k-reverse-problem-if-the-last-set-has-less-than-k-elements-what-will-you-do-krl","type":4},{"id":"80fc653c-64cb-464a-96b1-071e97b48a32","name":"What is the space complexity of K reverse in a linked list?(Q- KRL)","slug":"what-is-the-space-complexity-of-k-reverse-in-a-linked-list-q-krl","type":4},{"id":"ba618aad-140d-4d07-875e-01fc547d7b28","name":"If the size of the linked list is greater than the value of k, how will you add the elements in the new list?(Q- KRL)","slug":"if-the-size-of-the-linked-list-is-greater-than-the-value-of-k-how-will-you-add-the-elements-in-the-new-list-q-krl","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":"d2da6b99-4588-4cb8-8ff2-a897b6126768","name":"K Reverse In Linked List","slug":"k-reverse-in-linked-list","type":1}],"next":{"id":"ab9832c9-f9a2-412d-b490-450cdbccae79","name":"K Reverse In Linked List","type":3,"slug":"k-reverse-in-linked-list"},"prev":{"id":"f44f094e-36f7-453a-9395-c25ff791db29","name":"Odd Even Linked List","type":3,"slug":"odd-even-linked-list"}}}
plane

Editor


Loading...

K Reverse In Linked List

easy

1. You are given a partially written LinkedList class. 2. You are required to complete the body of kReverse function. The function is expected to tweak the list such that all groups of k elements in the list get reversed and linked. If the last set has less than k elements, leave it as it is (don't reverse). 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

11 1 2 3 4 5 6 7 8 9 10 11 3 100 200

Sample Output

1 2 3 4 5 6 7 8 9 10 11 3 2 1 6 5 4 9 8 7 10 11 100 3 2 1 6 5 4 9 8 7 10 11 200

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode