Similar Problems
Similar Problems not available
Printing distinct elements in a sorted linked list - Leetcode Solution
Companies:
LeetCode: Printing distinct elements in a sorted linked list Leetcode Solution
Difficulty: Unknown
Topics: linked-list
Given a linked list sorted in ascending order, print only the distinct elements in the linked list with only one pass through the linked list and without using more than O(1)
space.
Example Test Cases
Sample Test Case 1
Input Linked List: Given a linked list like this 1->2->2->3->3->4
Expected Output: 1->2->3->4
(since, there are 4 distinct values in the linked list). Only the first 4 elements need to be outputted.
Sample Test Case 2
Input Linked List 5->8->9->9->10
Expected Output: 5->8->9->10
Solution
Since the array is sorted, duplicate numbers will occur together at consecutive positions, and we need to choose only one of them. Therefore, to solve this problem 2 pointer method can be used.
We can create one fast pointer which moves by 1 element at each step one slow pointer which moves only when the fast pointer moves on to a new element. Now, whenever the values of fast pointer and slow pointer differ we print the distinct value and move the slow pointer to the location of fast pointer.
Take a look below:
Printing distinct elements in a sorted linked list Solution Code
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef struct node {
5 int data;
6 node* next;
7} node;
8
9/* Initially HEAD is null because list is empty */
10node* HEAD = NULL;
11
12// Inserts a node with data at the end of current linked list
13void insertAtTheEnd(int data) {
14
15 /* Step 1: Create a New Node dynamically by using new operator */
16 node* nodeToBeInserted = new node;
17 nodeToBeInserted->data = data;
18 nodeToBeInserted->next = NULL; /* Since, the node is getting inserted at the last, it's next will be NULL */
19
20 /* If head is NULL, then this is the first node that is getting inserted */
21 if (HEAD == NULL) {
22 HEAD = nodeToBeInserted;
23 }
24 else {
25 /* At the end of this loop, curr will point to the last node */
26 node* curr = HEAD;
27 while (curr->next != NULL) {
28 curr = curr->next;
29 }
30 /* Attach the nodeToBeInserted to the end of last node (curr) */
31 curr->next = nodeToBeInserted;
32 }
33}
34
35void printList() {
36 node* curr = HEAD;
37 while (curr != NULL) {
38 cout << curr->data << "\n";
39 curr = curr->next;
40 }
41}
42
43void printOnlyDistinct() {
44 /* Create two pointers, slow and fast pointer */
45 node* sp = HEAD, *fp = HEAD;
46 while (fp != NULL) {
47 if (sp == fp) {
48 cout << sp->data << "\n";
49 }
50 fp = fp->next;
51 if (fp != NULL && fp->data != sp->data) {
52 sp = fp;
53 }
54 }
55}
56
57int main() {
58
59 /** Creating the linked list */
60 insertAtTheEnd(5);
61 insertAtTheEnd(10);
62 insertAtTheEnd(10);
63 insertAtTheEnd(15);
64 insertAtTheEnd(15);
65
66 /** Printing all the elements of the list */
67 cout << "Printing all the elements\n";
68 printList();
69
70 /** Printing only the distinct elements of the list */
71 cout << "Printing only distinct elements \n";
72 printOnlyDistinct();
73
74 return (0);
75}