{"id":"f4628166-bc58-43d3-a2c3-268db95a91ad","name":"Remove Duplicates In A Sorted Linked List","description":" 1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of removeDuplicates function. The function is called on a sorted list. The function must remove all duplicates from the list in linear time and constant space\r\n3. Input and Output is managed for you. \r\n ","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\nclass Node\n{\npublic:\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 \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 }\npublic:\n void removeDuplicates() {\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\n cout << l.toString() << endl;\n l.removeDuplicates();\n cout << l.toString() << endl;\n\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 // 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 l1.display();\r\n l1.removeDuplicates();\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# remove duplicates\n\n def removeDuplicates(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 \n\n\nll.display()\nll.removeDuplicates()\nll.display()"}},"points":10,"difficulty":"easy","sampleInput":"10\r\n2 2 2 3 3 5 5 5 5 5","sampleOutput":"2 2 2 3 3 5 5 5 5 5 \r\n2 3 5 \r\n","questionVideo":"https://www.youtube.com/embed/T4Od7rqE2BM","hints":[],"associated":[],"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":"7d5d85b2-e6ef-4239-8cfc-ef05431436e7","name":"Remove Duplicates In A Sorted Linked List","slug":"remove-duplicates-in-a-sorted-linked-list","type":1}],"next":{"id":"14b0e902-0f5e-45ad-87e1-477d7d478e52","name":"Remove Duplicates in Sorted Linked List","type":3,"slug":"remove-duplicates-in-sorted-linked-list"},"prev":{"id":"606e4260-0539-4fec-a42a-b7a653a9dfa2","name":"Merge Sort A Linked List","type":3,"slug":"merge-sort-a-linked-list"}}}

Remove Duplicates In A Sorted Linked List

1. You are given a partially written LinkedList class. 2. You are required to complete the body of removeDuplicates function. The function is called on a sorted list. The function must remove all duplicates from the list in linear time and constant space 3. Input and Output is managed for you.

{"id":"f4628166-bc58-43d3-a2c3-268db95a91ad","name":"Remove Duplicates In A Sorted Linked List","description":" 1. You are given a partially written LinkedList class.\r\n2. You are required to complete the body of removeDuplicates function. The function is called on a sorted list. The function must remove all duplicates from the list in linear time and constant space\r\n3. Input and Output is managed for you. \r\n ","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\nclass Node\n{\npublic:\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 \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 }\npublic:\n void removeDuplicates() {\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\n cout << l.toString() << endl;\n l.removeDuplicates();\n cout << l.toString() << endl;\n\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 // 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 l1.display();\r\n l1.removeDuplicates();\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# remove duplicates\n\n def removeDuplicates(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 \n\n\nll.display()\nll.removeDuplicates()\nll.display()"}},"points":10,"difficulty":"easy","sampleInput":"10\r\n2 2 2 3 3 5 5 5 5 5","sampleOutput":"2 2 2 3 3 5 5 5 5 5 \r\n2 3 5 \r\n","questionVideo":"https://www.youtube.com/embed/T4Od7rqE2BM","hints":[],"associated":[],"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":"7d5d85b2-e6ef-4239-8cfc-ef05431436e7","name":"Remove Duplicates In A Sorted Linked List","slug":"remove-duplicates-in-a-sorted-linked-list","type":1}],"next":{"id":"14b0e902-0f5e-45ad-87e1-477d7d478e52","name":"Remove Duplicates in Sorted Linked List","type":3,"slug":"remove-duplicates-in-sorted-linked-list"},"prev":{"id":"606e4260-0539-4fec-a42a-b7a653a9dfa2","name":"Merge Sort A Linked List","type":3,"slug":"merge-sort-a-linked-list"}}}
plane

Editor

Loading...

Remove Duplicates In A Sorted Linked List

easy

1. You are given a partially written LinkedList class. 2. You are required to complete the body of removeDuplicates function. The function is called on a sorted list. The function must remove all duplicates from the list in linear time and constant space 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

10 2 2 2 3 3 5 5 5 5 5

Sample Output

2 2 2 3 3 5 5 5 5 5 2 3 5

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode