Cracking the coding interview--Q2.1

原文:
Write code to remove duplicates from an unsorted linked list.FOLLOW UPHow would you solve this problem if a temporary buffer is not allowed?
訳文:
チェーンテーブルの重複要素を削除し、
また、一時的なストレージスペースを使用しない場合はどうすればいいですか?
回答:
スペースに制限がない場合は、チェーンテーブルに現れた要素をmapでマークし、チェーンテーブルを最初から最後までスキャンして、現れた要素を削除すればいいです.時間複雑度O(n).
空間を制限する場合、2つのポインタn,mを設定することができ、nがある要素を指す場合、mはその要素の後ろにある同じ要素を削除し、時間複雑度O(n 2)を設定することができる.

import java.util.HashMap;



public class List {

    int data;

    List next;



    public List(int d) {

        this.data = d;

        this.next = null;

    }



    void appendToTail(int d) {

        List end = new List(d);

        List n = this;

        while (n.next != null) {

            n = n.next;

        }

        n.next = end;

    }



    void print() {

        List n = this;

        System.out.print("{");

        while (n != null) {

            if (n.next != null)

                System.out.print(n.data + ", ");

            else

                System.out.println(n.data + "}");

            n = n.next;

        }

    }



    void removeDuplicate() {

        HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();

        List n = this;

        map.put(Integer.valueOf(n.data), true);

        while (n.next != null) {

            if (map.containsKey(Integer.valueOf(n.next.data))) {

                n.next = n.next.next;

            } else {

                map.put(Integer.valueOf(n.next.data), true);

                n = n.next;

            }

        }

    }



    void removeDuplicate1() {

        List n = this;

        List m;

        while (n != null) {

            m = n;

            while (m.next != null) {

                if(m.next.data == n.data)

                    m.next = m.next.next;

                else

                    m = m.next;

            }

            n = n.next;

        }

    }



    public static void main(String args[]) {

        List list = new List(0);

        list.appendToTail(1);

        list.appendToTail(2);

        list.appendToTail(2);

        list.appendToTail(3);

        list.appendToTail(3);

        list.appendToTail(4);

        list.appendToTail(1);

        list.appendToTail(2);

        list.appendToTail(0);

        list.print();

        //list.removeDuplicate();

        list.removeDuplicate1();

        list.print();

    }

}