JZ56：删除链表中重复的结点（不保留/保留）

删除有序链表中重复出现的元素（不保留）

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.
```
输入
{1,2,2}
返回值
{1}
```
解法1：伪结点&双指针
1.设置伪结点，方便处理
2.双指针pre和cur
3.当遇到当前节点值和下一节点值相等的节点时，进行while循环找到下一个不相等的节点，挂到prev节点上

4.当遇到当前节点值和下一节点值不相等的节点时，prev和curr都移动到下一个节点接着遍历就行

public ListNode deleteDuplicates(ListNode head) {
  ListNode dummy = new ListNode(-1);
  dummy.next = head;

  ListNode prev = dummy;
  ListNode curr = head;
  while (curr != null && curr.next != null) {
      if (curr.val == curr.next.val) {
          ListNode temp = curr.next;
          while (temp != null && temp.val == curr.val) {
              temp = temp.next;
          }

          prev.next = temp;
          curr = temp;
      } else {
          prev = prev.next;
          curr = curr.next;
      }
  }
  return dummy.next;
}

解法2：使用set

分析
多次遍历，第一次遍历把重复的结点值存入 set 容器，第二次遍历，当结点值存储在 set 容器中，就删除该结点

代码

import java.util.*;
public class Solution {
 public ListNode deleteDuplication(ListNode pHead){
     if(pHead == null){
         return  null;
     }
     // 先找出相同结点，存入 set
     HashSet<Integer> set = new HashSet<>();
     ListNode pre = pHead;
     ListNode cur = pHead.next;
     while(cur != null){
         if(cur.val == pre.val){
             set.add(cur.val);
         }
         pre = cur;
         cur = cur.next;
     }
     // 再根据相同节点删除
     // 先删头部
     while(pHead != null && set.contains(pHead.val)){
         pHead = pHead.next;
     }
     if(pHead == null){
         return null;
     }
     // 再删中间结点
     pre = pHead;
     cur = pHead.next;
     while(cur != null){
         if(set.contains(cur.val)){
             pre.next = cur.next;
             cur = cur.next;
         }else{
             pre = cur;
             cur = cur.next;
         }
     }
     return pHead;
 }
}

复杂度

时间复杂度：HashSet 是基于哈希表实现的，查找效率为 O(1)，所以总的效率是 O(n)
空间复杂度：最坏的情况是存一半结点 O(n/2)，最好的情况是一个也不存，O(1)

删除有序链表中重复的元素（保留）

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次

给出的链表为1→1→2,返回> 1→2.
给出的链表为1→1→2→3→3,返回1→2→3.
```
输入 {1,1,2}
输出 {1,2
```
解法1：伪结点&双指针
1.设置伪结点，方便处理
2.双指针pre和cur
3.当遇到当前节点值和下一节点值相等的节点时，进行while循环跳过节点，挂到pre节点上

4.当遇到当前节点值和下一节点值不相等的节点时，prev和curr都移动到下一个节点接着遍历就行

public ListNode deleteDuplicates(ListNode head) {
  ListNode dummy = new ListNode(-1);
  dummy.next = head;

  ListNode prev = dummy;
  ListNode curr = head;
  while (curr != null && curr.next != null) {
      if (curr.val == curr.next.val) {
          ListNode temp = curr.next;

           while(temp.next != null && temp.next.val == cur.val) {
              temp.next = temp.next.next;
          }

          prev.next = temp;
          curr = temp;
      } else {
          prev = prev.next;
          curr = curr.next;
      }
  }
  return dummy.next;
}

解法2：迭代

解题思路：
用cur表示当前节点，利用wile循环遍历链表
结束条件为: 遍历完链表，即 cur.next 为空; 头结点 head 可能为空, 则也需要判断 cur 是否为空
遍历过程中：
(1)如果该节点出元素与下一节点元素相同，则删除下一节点: cur.next = cur.next.next;
(2)若不同，则继续遍历;
细节分析：
需要判断 head 是否为空:
(1) 可在开头判断 head 是否为空
(2) 也可在 while 循环中判断 cur 是否为空
为什么如果前后两节点元素相同，删除后节点，而不用 cur = cur.next 操作？
答：是因为删除该节点的下一节点，该节点仍需要和新的下一节点进行比较

时间复杂度：O(n)O(n)，因为列表中的每个结点都检查一次以确定它是否重复，所以总运行时间为 O(n)O(n)，其中 nn 是列表中的结点数。
空间复杂度：O(1)O(1)，没有使用额外的空间。

    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head==null || head.next==null){
            return head;
        }
        ListNode cur = head;
        while(cur.next!=null){
            if(cur.val==cur.next.val){
                cur.next=cur.next.next;
            }
            else{
                cur=cur.next;
            }
        }
        return head;
    }

解法3：递归

递归写法的删除节点操作是通过返回下一节点连接到上一节点，实现参数节点(即当前节点)的删除

递归的三步法:
参数 head 的含义为当前节点

终止条件: 遍历完链表
(1) head.next 为空
(2) head 为空，即空链表
终止处理: 返回当前节点

提取重复逻辑:
(1) 节点的"连接": 利用函数返回值作为下一节点
(2) 节点的"删除": 判断是否当前节点元素与下一节点元素是否相同, 返回相应的节点

public ListNode deleteDuplicates (ListNode head) {
     // write code here
     if(head==null || head.next==null){
         return head;
     }
     head.next=deleteDuplicates(head.next);
     return head.val==head.next.val ? head.next : head;
 }