Printing distinct elements in a sorted linked list - Leetcode Solution

Companies:

Adobe

LeetCode: Printing distinct elements in a sorted linked list Leetcode Solution

Difficulty: Unknown

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: