删除无序单链表中值重复出现的节点 & 在单链表中删除指定值的节点

删除无序单链表中值重复出现的节点

题目：删除无序链表中值重复出现的节点

《程序员代码面试指南》第23题 P77 难度：士★☆☆☆

该题要求实现2种方法：

1. 时间复杂度O(N)
2. 额外空间复杂度O(1)

根据之前题，第一种解法我首先就想到了HashMap结构。不过这题只需要使用Set就行。

核心是判断当前节点的值是否已经在集合中，是则之前已经有该值了，需将其删除；不是则将其添加到集合中。

书上代码如下：

public void removeRep1(Node head) {
    if (head == null) {
      	return;
    }
    HashSet set = new HashSet();
    Node pre = head;
    Node cur = head.next;
    set.add(head.value);
    while (cur != null) {
        if (set.contains(cur.value)) {
          	pre.next = cur.next;
        } else {
          	set.add(cur.value);
          	pre = cur;
        }
        cur = cur.next;
    }
}

第二种解法额外空间复杂度为O(1)。因为在判断当前节点的值是否重复时，肯定要与先前的已存在且不重复的值作比较。

那肯定得有存放之前值的容量（否则怎么知道当前值在之前是否已经出现呢？），那么额外空间复杂度必然会达到O(N)。

所以如果要实现额外空间复杂度为O(1)，那只能通过N次遍历来实现了，每次遍历与一个值作比较，删除与值与该值重复的节点。不过这样时间复杂度就达到了O(N2)。

具体代码如下：

public void removeRep2(Node head) {
    Node cur = head;
    Node pre = null;
    Node next = null;
    while (cur != null) {
        pre = cur;
        next = cur.next;
        while (next != null) {
            if (cur.value == next.value) {
              	pre.next = next.next;
            } else {
              	pre = next;
            }
            next = next.next;
        }
        cur = cur.next;
    }
}

在单链表中删除指定值的节点

题目：在链表中删除指定值的节点

《程序员代码面试指南》第24题 P79 难度：士★☆☆☆

本题还是两种解法，第一种还是用栈或其他容器收集节点的方法，故额外空间复杂度为O(N)。

将值不等于num的节点用栈收集起来，最后弹出的过程中再逐一连接即可。最后将栈底元素作为新的头结点返回。

代码如下：

public Node removeValue1(Node head, int num) {
    Stack stack = new Stack();
    while (head != null) {
        if (head.value != num) {
            stack.push(head);
        }
        head = head.next;
    }
    while (!stack.isEmpty()) {
        stack.peek().next = head;
        head = stack.pop();
    }
    return head;
}

第二种则直接在链表上调整，额外空间复杂度为O(1)。

首先从链表头开始，找到第一个值不为num的节点，作为新的头结点；

然后往后遍历，不断删除值为num的节点。注意pre与cur节点的调整即可。

代码如下：

public static Node removeValue2(Node head, int num) {
    while (head != null) {
        if (head.value != num) {
            break;
        }
        head = head.next;
    }
    Node pre = head;
    Node cur = head;
    while (cur != null) {
        if (cur.value == num) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}