题目主要信息

1、在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

2、进阶：空间复杂度 ，时间复杂度

方法一：递归

具体方法

递归函数直接使用题目给出的函数 deleteDuplication，它的含义是 删除以 head 作为开头的有序链表中，值出现重复的节点。

递归终止条件 终止条件就是能想到的基本的、不用继续递归处理的case。如果 head 为空，那么肯定没有值出现重复的节点，直接返回 head； 如果 head.next 为空，那么说明链表中只有一个节点，也没有值出现重复的节点，也直接返回 head。

什么时候需要递归呢?

• 如果 head.val != head.next.val ，说明头节点的值不等于下一个节点的值，所以当前的 head 节点必须保留；但是 head.next 节点要不要保留呢？我们还不知道，需要对 head.next 进行递归，即对 head.next 作为头节点的链表，去除值重复的节点。所以 head.next = deleteDuplication(head.next).
• 如果 head.val == head.next.val ，说明头节点的值等于下一个节点的值，所以当前的 head 节点必须删除，并且 head 之后所有与 head.val 相等的节点也都需要删除；删除到哪个节点为止呢？需要用 move 指针一直向后遍历寻找到与 head.val 不等的节点。此时 move 之前的节点都不保留了，因此返回 deleteDuplication(move);

题目让我们返回删除了值重复的节点后剩余的链表，结合上面两种递归调用的情况。

如果 head.val != head.next.val ，头结点需要保留，因此返回的是 head； 如果 head.val == head.next.val ，头结点需要删除，需要返回的是 deleteDuplication(move);。 对链表 1 -> 2 -> 2 -> 3 递归的过程如下。

Java代码

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) return pHead;

        //如果 head.val != head.next.val 
        if (pHead.val != pHead.next.val) {
          
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        } else {
            //如果 head.val == head.next.val 
            ListNode tmp = pHead;
            while (tmp != null && tmp.val == pHead.val) tmp = tmp.next;
            return deleteDuplication(tmp);
        }
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，每个节点访问了一次。
• 空间复杂度：$O(n)O(n)$，递归调用的时候会用到了系统的栈。

方法二：直接遍历删除

具体方法

在遍历的过程中如果当前节点cur与下一个结点相等，就借助while循环，一直遍历到不相等的位置，cur的前节点pre指向当前cur的节点的下一个。

比如0-2-3-3-3-5 ；pre指向2 ，cur指向第一个3， 一直遍历到cur.next指向5，此时让pre.next = cur.next 即可。

Java代码

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode result = new ListNode(0);
        result.next = pHead;
        
        ListNode pre = result,cur = pHead;
        //if(pHead==null||pHead.next==null) return pHead;//处理特殊情况
        while(cur!=null&&cur.next!=null ){
            if(cur.val == cur.next.val){
                //清除所有相等的元素
                while(cur.next!=null && cur.val==cur.next.val){
                    cur = cur.next;
                }
                //pre指向最后一个相等元素的下一个
                pre.next = cur.next;
                //cur指向下一个元素
                cur = cur.next;
            }else{
                //当没有遇到相等的时候
                pre = cur;
                cur = cur.next;
            }
        }
        return result.next;
    }
}

复杂度分析

• 时间复杂度：$O(n)O(n)$，只需要遍历一次链表即可。
• 空间复杂度：$O(1)O(1)$，存结果的变量