Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. In a sorted list, duplicates are next to each other.
  2. 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