筛选重复值只保留一个（表格筛选重复值只保留一个）

题目描述：

给定一个没有排序的链表，去掉其重复项，并保留原来顺序。例如链表1->3->1->5->5->7，去掉重复项后变为1->3->5->7

方法一：顺序删除

通过双重循环在链表上执行删除操作。外层循环用一个指针从第一个节点开始遍历整个链表，然后内层循环用另一个指针遍历其余节点，将与外层循环遍历到的指针所指节点的数据域相同的节点删除

假设外层循环从outerCur开始遍历，当内层循环指针innerCur到上图实线所示位置outerCur.v%alue==innerCur.value时，此时需要将innerCur指向的节点删除。具体步骤如下

1、用tmp记录待删除的节点地址

2、为了能够在删除tmp节点后继续遍历链表中其余节点，使innerCur指针指向他的后继节点，innerCur=innerCur.next。

3、从链表中删除tmp节点。

public static void removeDup(Node head) {
        if (head == null || head.next == null){
            return;
        }
        Node outerCur = head.next;
        Node innerCur;
        Node innerPre;
        for(;outerCur != null;outerCur = outerCur.next){
            for (innerCur = outerCur.next,innerPre = outerCur;innerCur != null;) {
                if (outerCur.value == innerCur.value) {
                    innerPre.next = innerCur.next;
                } else {
                    innerPre = innerCur;
                }
                innerCur = innerCur.next;
            }
        }
    }
public static void main(String[] args) {
        int i = 1;
        Node head = new Node();
        head.next = null;
        Node tmp = null;
        Node cur = head;

        for (;i<7;i++) {
            tmp = new Node();
            if (i % 2 == 0) {
                tmp.value = i +1;
            } else if (i % 3 == 0) {
                tmp.value = i -2;
            } else {
                tmp.value = i;
            }
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        System.out.println("删除前");
        for (cur = head.next;cur != null;cur = cur.next) {
            System.out.print(cur.value + " ");
        }
        System.out.println();
        removeDup(head);
        System.out.println("删除后");
        for (cur = head.next;cur!= null;cur = cur.next) {
            System.out.print(cur.value + " ");
        }
    }

性能分析：

由于采用双重遍历，因此时间复杂度为O（N^2）。在遍历链表过程中使用了常量个额外的指针变量来保存当前遍历的节点、前驱节点和被删除的节点，因此空间复杂度为O(1)。

方法二：递归法

主要思路为对于节点cur，首先递归的删除以cur.next为首的子链表中重复的节点，接着从以cur.next为首的子链表中找出与cur有着相同数据域的节点并删除。

private static Node removeDupSub(Node head) {
        if (head.next == null) {
            return head;
        }
        Node pointer = null;
        Node cur = head;
        head.next = removeDupSub(head.next);
        pointer = head.next;
        while (pointer != null) {
            if (head.value == pointer.value) {
                cur.next = pointer.next;
                pointer = cur.next;
            } else {
                pointer = pointer.next;
                cur = cur.next;
            }
        }
        return head;
    }

    public static void removeDup2(Node head) {
        if (head == null) {
            return;
        }
        head.next = removeDupSub(head.next);
    }

性能分析:

与方法一类似，需要对链表进行双重遍历，时间复杂度为O(N^2)，由于递归会增加许多额外的函数调用，理论上将该方法比效率比方法一低一些。

方法三：空间换时间

为了降低时间复杂度，在条件允许的情况下使用辅助空间例如

1、建立一个HashSet，HashSet中内容为已经遍历过的节点内容

2、从头开始遍历，如果节点内容已经存在HashMap中，删除次节点，继续遍历；如果不在HashSet中，保留次节点，将此节点添加到HashSet中继续遍历。

标签： com