面试题 02.01. 移除重复节点。编写代码,移除未排序链表中的重复节点。保留最开始出现的节点
移除重复节点
哈希表
我们对给定的链表进行一次遍历,并用一个哈希集合(HashSet)来存储所有出现过的节点。由于在大部分语言中,对给定的链表元素直接进行「相等」比较,实际上是对两个链表元素的地址(而不是值)进行比较。因此,我们在哈希集合中存储链表元素的值,方便直接使用等号进行比较。
具体地,我们从链表的头节点head
开始进行遍历,遍历的指针记为 cur
。由于头节点一定不会被删除,因此我们可以枚举待移除节点的前驱节点,减少编写代码的复杂度。
这样枚举有什么好处?试想一下,如果我们直接枚举待移除节点,那么在将它进行移除时,我们本质上是将它的前驱节点连向后继节点。而由于题目给定的链表结构中,我们无法直接访问一个节点的前驱节点。因此,我们不如直接枚举前驱节点 cur
,那么节点本身就是cur .next
,后继节点就是 cur.next.next
。
在遍历完成后,我们就得到了最终的答案链表。
//面试题 02.01. 移除重复节点 //编写代码,移除 未排序 表中的重复节点。保留最开始出现的节点。 public ListNode removeDuplicateNodes() { if (head == null) return null; Set<Integer> set = new HashSet<>(); set.add(head.val); ListNode cur = head; while (cur.next != null) { ListNode curNext = cur.next; if (set.add(curNext.val)) { cur = cur.next; } else { cur.next = cur.next.next; } } //cur.next = null; return head; }
测试:
public static void main(String[] args) { MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addLast(1); myLinkedList.addLast(2); myLinkedList.addLast(2); myLinkedList.addLast(3); myLinkedList.addLast(3); ListNode ret = myLinkedList.removeDuplicateNodes(); myLinkedList.display(ret); }