1. 删除排序链表中的重复元素

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。

思路：

  • 已满足链表为升序，那么直接通过判断下一个节点是否与前一个节点权值相同来决定是否删除。

    1. class Solution {
    2.   public ListNode deleteDuplicates(ListNode head) {
    3.       ListNode cur = head;
    4.       while(cur!=null && cur.next!=null){
    5.           if(cur.val==cur.next.val){
    6.               cur.next = cur.next.next;
    7.           }else{
    8.               cur = cur.next;
    9.           }
    10.       }
    11.       return head;
    12.   }
    13. }

  • 非升序链表，可以通过Set的数据结构来进行操作：

    • 遍历链表，每一次遍历判断set中是否含有该元素（节点权值），如果没有就添加到set中，然后继续扫描；如果有，那么删除该节点。
      1. class Solution {
      2. public ListNode deleteDuplicates(ListNode head) {
      3.    if(head==null){
      4.        return head;
      5.    }
      6.    Set<Integer> set = new HashSet<>();
      7.    ListNode temp = head;
      8.    set.add(head.val);
      9.    while(temp!=null&&temp.next!=null){
      10.        if(!set.contains(temp.next.val)){
      11.            set.add(temp.next.val);
      12.            temp = temp.next;
      13.        }else{
      14.            temp.next = temp.next.next;
      15.        }
      16.    }
      17.    return head;
      18. }
      19. }

  • 需要注意的是：

    • 单链表节点的删除必须依靠辅助指针，也就是通过指向该节点上一个节点的指针指向被删节点的下一个节点来完成。