题解 | #删除链表中重复的结点#

多年不刷题 刷了链表的几个 这居然是第一个一遍ac的 绝了

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/

// 该问题其实就是删除链表中节点的问题 首先知道需要删除哪些节点 其次特殊处理首节点被删除的情况即可
// 需要三个指针 其中一个 首节点可能被删除 需要一个头指针记录处理
// 1->1->1
// 1->1->1->2
// 1->1->1->2->2->3->4
// 1->2->2->3->4->4->5
import java.util.HashSet;
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
    	// 求出重复的节点
    	HashSet<Integer> all = new HashSet<>();
    	HashSet<Integer> ansSet = new HashSet<>();
    	ListNode tmp = pHead;
    	while(tmp != null) {
    		if (!all.add(tmp.val)) {
    			ansSet.add(tmp.val);
    		}
            tmp = tmp.next;
    	}

    	// 很多问题需要设置 头指针 特殊处理首节点
    	ListNode head = new ListNode(-1);
    	head.next = pHead;

    	// 删除链表的节点 p q 
    	ListNode p = head;
    	ListNode q = pHead;

    	while (q != null) {
    		// q节点需要被删除
    		if (ansSet.contains(q.val)) {
    			// 删除q节点
    			p.next = q.next;
    			// 注意：如果是头节点指向的节点***掉 需要更新头节点 以记录当前链表的首节点在哪里
    			if (head.next == q) {
    				head.next = q.next;
    			}
    			// q移动 但p不动!
    			q = q.next;
    		} else {
    			// q节点不需要被删除 p q同时移动!
    			p = q;
    			q = q.next;
    		}
    	}

    	return head.next;
    }
}