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

---

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

• 描述:存在一个按升序排列的链表，给你这个链表的头节点head，请你删除所有重复的元素，使每个元素只出现一次。 例如：

  输入：head = [1,1,2,3,3]
  输出：[1,2,3]

  

解法

• 使用一个指针解决

• 既然是排过序的，那么相同的节点肯定是挨着的。我们可以使用一个指针cur，每次都要判断是否和他后面的节点值相同，如果相同就把后面的那个节点给删除。*

代码如下：

public ListNode deleteDuplicates(ListNode head) {
    //如果但前节点是空，或者是单个节点，直接返回
    if (head == null || head.next == null)
        return head;
    //只用一个指针cur指向当前节点
    ListNode cur = head;
    while (cur.next != null) {
        //如果当前节点的值和下一个节点的值相同，
        //就把下一个节点值给删除
        if (cur.val == cur.next.val) {
            cur.next = cur.next.next;
        } else {
            //否则cur就往后移一步
            cur = cur.next;
        }
    }
    return head;
}

---

• 递归方式解决
  以输入链表为 head=[1,1,2,3,3]为例，下图为理解图：
  <img =src=”/img/coding/deleteListNode1.png” alt=”deleteListNode1” style:”zoom: 65%;” />

代码如下：

public ListNode deleteDuplicates(ListNode head){
    //递归的边界条件判断
    if (head == null || head.next == null)
        return head;
    //递归，相当于从后往前遍历
    head.next = deleteDuplicates(head.next);
    //如果当前节点和下一个一样，直接返回下一个节点，否则
    //返回当前节点
    return head.val == head.next.val ? head.next : head;
}

---

---

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

• 描述：存在一个按升序排列的链表，给你这个链表的头节点head，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。返回同样按升序排列的结果链表。
  例如：

  输入：head = [1,2,3,3,4,4,5]
  输出：[1,2,5]

  

解法：

• 双指针解决
  这题的解决思路就是使用两个指针，一个指针cur指向当前节点，一个指针pre指向当前节点cur的前一个节点。cur始终和他的下一个节点比较，如果相同就往后移，如果不相同我们就需要判断pre的下一个节点是否是cur，如果是cur说明没有相同的节点，如果不是cur说明有相同的节点.
  来看一下代码：

  public ListNode deleteDuplicates(ListNode head) {
      if(head==null || head.next==null){
      	return null;
      }
      //添加一个dummy节点
      ListNode dummy=new ListNode(0);
      //让dummy节点的next指针指向head。
      dummy.next=head;
      //指向当前遍历的节点
      ListNode cur=head;
      //指向当前节点pre的前一个节点
      ListNode pre=dummy;
      while(cur!=null){
      	while(cur.next!=null && cur.next.val==cur.val){
  	     //如果有重复的，cur就一直往下走
  	     cur=cur.next;
     	 }
  	//判断上面有没有重复的节点，如果pre.next == cur，说明没有
          //重复的节点。否则说明有重复的节点，然后还要把重复的节点给删除
      	if(pre.next==cur){
      	     pre=pre.next;
      	}else{
               //有重复的就删除
               pre.next=cur.next;
      	}
  	cur=cur.next;
      }
      return dummy.next;
  }

---

• 递归方式解决

  我们先定义一个函数deleteDuplicates(ListNode head)表示删除重复的节点。
  如果 head.val != head.next.val，也就是说当前节点和他的下一个节点值不一样，我们不做任何的删除，直接递归head节点的下一个节点，也就是

  head.next = deleteDuplicates(head.next);

  如果 head.val == head.next.val，说明有重复的节点，这里到底是重复一个还是重复多个，我们不知道，需要通过一个循环来确定。然后把重复的全部删除，也就是

  while (head.next != null && head.val == head.next.val)
      head = head.next;
  return deleteDuplicates(head.next);

那递归的终止条件是什么呢，就是节点为空，或者只有一个节点，这种情况下是不可能有重复的，直接返回即可。我们来看下完整代码:

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null)
        return head;
    if (head.val != head.next.val) {
        //如果当前节点和下一个节点的值不相同
        head.next = deleteDuplicates(head.next);
        return head;
    } else {
        //如果当前节点和下一个节点的值相同，说明出现了重复的，
        //把重复的全部给删除
        while (head.next != null && head.val == head.next.val)
            head = head.next;
        return deleteDuplicates(head.next);
    }
}