{"id":"e61e71a8-b34e-4884-b93b-0b013d592eac","name":"Fold A Linked List","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of fold function. The function is expected to place last element after 1st element, 2nd last element after 2nd element and so on. For more insight check the example\r\n\r\nExample 1\r\n1->2->3->4->5\r\nwill fold as\r\n1->5->2->4->3\r\n\r\nExample 2\r\n1->2->3->4->5->6\r\n1->6->2->5->3->4","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Time complexity -&gt; O(n)\r\n2. Space complexity -&gt; Recursion space, O(n)","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\n\nusing namespace std;\n\nclass node\n{\n public :\n int data;\n node *next;\n};\n\nclass linked_list\n{\nprivate:\n node *head, *tail;\n int size=0;\n \npublic:\n linked_list()\n {\n head = NULL;\n tail = NULL;\n }\n\n\n void addFirst(int val) {\n node* temp = new node();\n temp->data = val;\n temp->next = head;\n head = temp;\n\n if (size == 0) {\n tail = temp;\n }\n\n size++;\n }\n\n void add_node(int n)\n {\n node *tmp = new node;\n tmp->data = n;\n tmp->next = NULL;\n\n if(head == NULL)\n {\n head = tmp;\n tail = tmp;\n }\n else\n {\n tail->next = tmp;\n tail = tail->next;\n }\n size++;\n \n \n }\n void display(){\n for(node* tmp = head; tmp != NULL; tmp = tmp->next){\n cout<<tmp->data<<\" \";\n }\n cout<<endl;\n \n }\n \n node* pleft;\n int IsPalindromeHelper(node* right){\n if(right == NULL){\n return 1;\n }\n \n int rres = IsPalindromeHelper(right->next);\n if(rres == 0){\n return 0;\n } else if(pleft->data != right->data){\n return 0;\n } else {\n pleft = pleft->next;\n return 1;\n }\n }\n \n int isPalindrome(){\n pleft = head;\n return IsPalindromeHelper(head);\n }\n \n \n \n void fold() {\n // write your code here\n }\n}\n ;\n\nint main()\n{\n \n \n \n int b ;\n cin>>b;\n linked_list a;\n vector<int> arr(b,0);\n for(int i=0;i<b;i++)\n {\n \n cin>>arr[i];\n a.add_node(arr[i]);\n }\n int c;\n cin>>c;\n int d;\n cin>>d;\n a.display();\n a.fold();\n a.display();\n a.addFirst(c);\n a.add_node(d);\n a.display();\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 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 LinkedList prev = null;\r\n\r\n while (this.size > 0) {\r\n LinkedList curr = new LinkedList();\r\n\r\n if (this.size >= k) {\r\n for (int i = 0; i < k; i++) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n curr.addFirst(val);\r\n }\r\n } else {\r\n int sz = this.size;\r\n for (int i = 0; i < sz; i++) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n curr.addLast(val);\r\n }\r\n }\r\n\r\n if (prev == null) {\r\n prev = curr;\r\n } else {\r\n prev.tail.next = curr.head;\r\n prev.tail = curr.tail;\r\n prev.size += curr.size;\r\n }\r\n }\r\n\r\n this.head = prev.head;\r\n this.tail = prev.tail;\r\n this.size = prev.size;\r\n }\r\n\r\n private void displayReverseHelper(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n displayReverseHelper(node.next);\r\n System.out.print(node.data + \" \");\r\n }\r\n\r\n public void displayReverse() {\r\n displayReverseHelper(head);\r\n System.out.println();\r\n }\r\n\r\n private void reversePRHelper(Node node) {\r\n if (node == tail) {\r\n return;\r\n }\r\n reversePRHelper(node.next);\r\n node.next.next = node;\r\n }\r\n\r\n public void reversePR() {\r\n reversePRHelper(head);\r\n Node temp = head;\r\n head = tail;\r\n tail = temp;\r\n tail.next = null;\r\n }\r\n\r\n public void fold() {\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.fold();\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 def __init__(self,d):\n self.data = d\n self.next = None\n\nclass LinkedList:\n def __init__(self,h,t,s):\n self.head = h\n self.tail = t\n self.size = s\n \n def addLast(self,val):\n temp = Node(val)\n if(self.size == 0):\n self.head = temp\n self.tail = temp\n else:\n self.tail.next = temp\n self.tail = temp\n self.size += 1\n\n def display(self):\n temp=self.head\n while(temp != None):\n print(temp.data,end=\" \")\n temp = temp.next\n \n left = None\n def isPalindromeHelper(self,node):\n if(node == None):\n self.left = self.head\n return True\n if(self.isPalindromeHelper(node.next) == False):\n return False\n if(node.data != self.left.data):\n return False\n self.left = self.left.next\n return True\n \n def isPalindrome(self):\n if(self.isPalindromeHelper(self.head) == True):\n print(\"PALINDROME\")\n else:\n print(\"NOT PALINDROME\")\n \n left2=None\n \n \n def fold(self):\n \n # write your code here\n \n\ndef main():\n l = LinkedList(None,None,0)\n n = int(input())\n values = list(map(int,input().split(\" \")))\n for i in range(n):\n l.addLast(values[i])\n l.display()\n print()\n first = int(input())\n last = int(input())\n l.fold()\n l.display()\n print()\n print(first,end=\" \")\n l.display()\n print(last)\n\nif __name__==\"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n1 2 3 4 5\r\n10\r\n20","sampleOutput":"1 2 3 4 5 \r\n1 5 2 4 3 \r\n10 1 5 2 4 3 20","questionVideo":"https://www.youtube.com/embed/qMFOU84GGW4","hints":[],"associated":[{"id":"29eb4a30-6112-46f0-bc83-0d27d4c7b25d","name":"What is the time complexity of above code(Q- Fal)","slug":"what-is-the-time-complexity-of-above-code-q-fal","type":4},{"id":"9efb9acf-c21e-4679-a0b9-2df10ddb690b","name":"In which recursive order all the operations will be done?(Q_ FAL)","slug":"in-which-recursive-order-all-the-operations-will-be-done-q-fal","type":4},{"id":"ac35b217-8e0e-47aa-8676-a244137588af","name":"What is the pseudo code for swapping the nodes ?(Q_ FAL)","slug":"what-is-the-pseudo-code-for-swapping-the-nodes-q-fal","type":4},{"id":"fd41475e-101e-44a3-8726-c3037f30a018","name":"Why have we declared the left pointer outside the function ?(Q- FAL)","slug":"why-have-we-declared-the-left-pointer-outside-the-function-q-fal","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":"80528fef-b2e6-4954-ad69-4ef73e6df753","name":"Fold A Linked List","slug":"fold-a-linked-list","type":1}],"next":{"id":"5632da27-deb5-480c-8668-2b2ae2ea5296","name":"Fold A Linked List","type":3,"slug":"fold-a-linked-list"},"prev":{"id":"871b8cd8-a986-4136-8ec7-b4a748210040","name":"Is Linked List A Palindrome","type":3,"slug":"is-linked-list-a-palindrome"}}}

Fold A Linked List

1. You are given a partially written LinkedList class. 2. You are required to complete the body of fold function. The function is expected to place last element after 1st element, 2nd last element after 2nd element and so on. For more insight check the example Example 1 1->2->3->4->5 will fold as 1->5->2->4->3 Example 2 1->2->3->4->5->6 1->6->2->5->3->4

{"id":"e61e71a8-b34e-4884-b93b-0b013d592eac","name":"Fold A Linked List","description":"1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of fold function. The function is expected to place last element after 1st element, 2nd last element after 2nd element and so on. For more insight check the example\r\n\r\nExample 1\r\n1->2->3->4->5\r\nwill fold as\r\n1->5->2->4->3\r\n\r\nExample 2\r\n1->2->3->4->5->6\r\n1->6->2->5->3->4","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"1. Time complexity -&gt; O(n)\r\n2. Space complexity -&gt; Recursion space, O(n)","sampleCode":{"cpp":{"code":"#include <bits/stdc++.h>\n\nusing namespace std;\n\nclass node\n{\n public :\n int data;\n node *next;\n};\n\nclass linked_list\n{\nprivate:\n node *head, *tail;\n int size=0;\n \npublic:\n linked_list()\n {\n head = NULL;\n tail = NULL;\n }\n\n\n void addFirst(int val) {\n node* temp = new node();\n temp->data = val;\n temp->next = head;\n head = temp;\n\n if (size == 0) {\n tail = temp;\n }\n\n size++;\n }\n\n void add_node(int n)\n {\n node *tmp = new node;\n tmp->data = n;\n tmp->next = NULL;\n\n if(head == NULL)\n {\n head = tmp;\n tail = tmp;\n }\n else\n {\n tail->next = tmp;\n tail = tail->next;\n }\n size++;\n \n \n }\n void display(){\n for(node* tmp = head; tmp != NULL; tmp = tmp->next){\n cout<<tmp->data<<\" \";\n }\n cout<<endl;\n \n }\n \n node* pleft;\n int IsPalindromeHelper(node* right){\n if(right == NULL){\n return 1;\n }\n \n int rres = IsPalindromeHelper(right->next);\n if(rres == 0){\n return 0;\n } else if(pleft->data != right->data){\n return 0;\n } else {\n pleft = pleft->next;\n return 1;\n }\n }\n \n int isPalindrome(){\n pleft = head;\n return IsPalindromeHelper(head);\n }\n \n \n \n void fold() {\n // write your code here\n }\n}\n ;\n\nint main()\n{\n \n \n \n int b ;\n cin>>b;\n linked_list a;\n vector<int> arr(b,0);\n for(int i=0;i<b;i++)\n {\n \n cin>>arr[i];\n a.add_node(arr[i]);\n }\n int c;\n cin>>c;\n int d;\n cin>>d;\n a.display();\n a.fold();\n a.display();\n a.addFirst(c);\n a.add_node(d);\n a.display();\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 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 LinkedList prev = null;\r\n\r\n while (this.size > 0) {\r\n LinkedList curr = new LinkedList();\r\n\r\n if (this.size >= k) {\r\n for (int i = 0; i < k; i++) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n curr.addFirst(val);\r\n }\r\n } else {\r\n int sz = this.size;\r\n for (int i = 0; i < sz; i++) {\r\n int val = this.getFirst();\r\n this.removeFirst();\r\n curr.addLast(val);\r\n }\r\n }\r\n\r\n if (prev == null) {\r\n prev = curr;\r\n } else {\r\n prev.tail.next = curr.head;\r\n prev.tail = curr.tail;\r\n prev.size += curr.size;\r\n }\r\n }\r\n\r\n this.head = prev.head;\r\n this.tail = prev.tail;\r\n this.size = prev.size;\r\n }\r\n\r\n private void displayReverseHelper(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n displayReverseHelper(node.next);\r\n System.out.print(node.data + \" \");\r\n }\r\n\r\n public void displayReverse() {\r\n displayReverseHelper(head);\r\n System.out.println();\r\n }\r\n\r\n private void reversePRHelper(Node node) {\r\n if (node == tail) {\r\n return;\r\n }\r\n reversePRHelper(node.next);\r\n node.next.next = node;\r\n }\r\n\r\n public void reversePR() {\r\n reversePRHelper(head);\r\n Node temp = head;\r\n head = tail;\r\n tail = temp;\r\n tail.next = null;\r\n }\r\n\r\n public void fold() {\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.fold();\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 def __init__(self,d):\n self.data = d\n self.next = None\n\nclass LinkedList:\n def __init__(self,h,t,s):\n self.head = h\n self.tail = t\n self.size = s\n \n def addLast(self,val):\n temp = Node(val)\n if(self.size == 0):\n self.head = temp\n self.tail = temp\n else:\n self.tail.next = temp\n self.tail = temp\n self.size += 1\n\n def display(self):\n temp=self.head\n while(temp != None):\n print(temp.data,end=\" \")\n temp = temp.next\n \n left = None\n def isPalindromeHelper(self,node):\n if(node == None):\n self.left = self.head\n return True\n if(self.isPalindromeHelper(node.next) == False):\n return False\n if(node.data != self.left.data):\n return False\n self.left = self.left.next\n return True\n \n def isPalindrome(self):\n if(self.isPalindromeHelper(self.head) == True):\n print(\"PALINDROME\")\n else:\n print(\"NOT PALINDROME\")\n \n left2=None\n \n \n def fold(self):\n \n # write your code here\n \n\ndef main():\n l = LinkedList(None,None,0)\n n = int(input())\n values = list(map(int,input().split(\" \")))\n for i in range(n):\n l.addLast(values[i])\n l.display()\n print()\n first = int(input())\n last = int(input())\n l.fold()\n l.display()\n print()\n print(first,end=\" \")\n l.display()\n print(last)\n\nif __name__==\"__main__\":\n main()"}},"points":10,"difficulty":"easy","sampleInput":"5\r\n1 2 3 4 5\r\n10\r\n20","sampleOutput":"1 2 3 4 5 \r\n1 5 2 4 3 \r\n10 1 5 2 4 3 20","questionVideo":"https://www.youtube.com/embed/qMFOU84GGW4","hints":[],"associated":[{"id":"29eb4a30-6112-46f0-bc83-0d27d4c7b25d","name":"What is the time complexity of above code(Q- Fal)","slug":"what-is-the-time-complexity-of-above-code-q-fal","type":4},{"id":"9efb9acf-c21e-4679-a0b9-2df10ddb690b","name":"In which recursive order all the operations will be done?(Q_ FAL)","slug":"in-which-recursive-order-all-the-operations-will-be-done-q-fal","type":4},{"id":"ac35b217-8e0e-47aa-8676-a244137588af","name":"What is the pseudo code for swapping the nodes ?(Q_ FAL)","slug":"what-is-the-pseudo-code-for-swapping-the-nodes-q-fal","type":4},{"id":"fd41475e-101e-44a3-8726-c3037f30a018","name":"Why have we declared the left pointer outside the function ?(Q- FAL)","slug":"why-have-we-declared-the-left-pointer-outside-the-function-q-fal","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":"80528fef-b2e6-4954-ad69-4ef73e6df753","name":"Fold A Linked List","slug":"fold-a-linked-list","type":1}],"next":{"id":"5632da27-deb5-480c-8668-2b2ae2ea5296","name":"Fold A Linked List","type":3,"slug":"fold-a-linked-list"},"prev":{"id":"871b8cd8-a986-4136-8ec7-b4a748210040","name":"Is Linked List A Palindrome","type":3,"slug":"is-linked-list-a-palindrome"}}}
plane

Editor

Loading...

Fold A Linked List

easy

1. You are given a partially written LinkedList class. 2. You are required to complete the body of fold function. The function is expected to place last element after 1st element, 2nd last element after 2nd element and so on. For more insight check the example Example 1 1->2->3->4->5 will fold as 1->5->2->4->3 Example 2 1->2->3->4->5->6 1->6->2->5->3->4

Constraints

1. Time complexity -> O(n) 2. Space complexity -> Recursion space, O(n)

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

5 1 2 3 4 5 10 20

Sample Output

1 2 3 4 5 1 5 2 4 3 10 1 5 2 4 3 20

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode