Practice › Linked List
Remove Duplicates from Sorted List
Easy · Linked List · Asked at Amazon, Microsoft, TCS, Infosys, Wipro
The linked list is sorted. Delete nodes so that each value appears only once, and print the list.
Input
First line: n. Second line: the n node values from head to tail.
Output
The list after removing duplicates.
Constraints
- 1 ≤ n ≤ 10^5
If the next node has the same value as the current one, skip it: cur.next = cur.next.next.
Example 1
Input
3 1 1 2
Output
1 2
Example 2
Input
5 1 1 2 3 3
Output
1 2 3
Hints
- In a sorted list, duplicates are next to each other.
- If cur.next has the same value as cur, unlink it; otherwise move cur forward.
Approach
Walk with cur. While cur.next exists: if its value equals cur.val, skip it (cur.next = cur.next.next) and stay on cur (there may be more copies); otherwise advance. Each node is looked at once.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next = nullptr;
Node(long long v) : val(v) {}
};
int main() {
int n;
cin >> n;
Node dummy(0), *t = &dummy;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
t = t->next = new Node(x);
}
for (Node *cur = dummy.next; cur && cur->next;) {
if (cur->next->val == cur->val) cur->next = cur->next->next;
else cur = cur->next;
}
for (Node *p = dummy.next; p; p = p->next) cout << p->val << (p->next ? " " : "\n");
return 0;
}Python solution
import sys
class Node:
def __init__(self, val):
self.val, self.next = val, None
data = list(map(int, sys.stdin.read().split()))
dummy = tail = Node(0)
for v in data[1 : 1 + data[0]]:
tail.next = Node(v)
tail = tail.next
cur = dummy.next
while cur and cur.next:
if cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.next
out, p = [], dummy.next
while p:
out.append(p.val)
p = p.next
print(*out)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node dummy = new Node(0), t = dummy;
for (int i = 0; i < n; i++) t = t.next = new Node(sc.nextLong());
Node cur = dummy.next;
while (cur != null && cur.next != null) {
if (cur.next.val == cur.val) cur.next = cur.next.next;
else cur = cur.next;
}
StringBuilder sb = new StringBuilder();
for (Node p = dummy.next; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
System.out.println(sb);
}
}Solve Remove Duplicates from Sorted List online · All practice problems