牛客NC24#删除有序链表中重复的元素-II#

题目链接

描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

题目很简单，因为给的是升序链表相同的都挨在一起，我们确定链表中一个值是否存在重复只需要判断他的前一项和后一项是否相同即可。同时因为我们在遍历的过程中因为只要确定第个元素是不重复的，那么一定不会等于第个元素。所以我们判断第个元素时只要判断其与第个元素之间的关系就好了。

方法一：删除链表内重复的值

解题思路：

我们只要依次遍历链表，然后判断遍历的元素是否重复，重复删除，否则留下即可。但是在遍历的时候我们会碰到第一个元素没有前一项以及最后一个元素没有后一项的情况，所以要单独拿出来。

所以：

1. 只需要和比较是否相等。
2. 需要和和比较是否相等。 &&
3. 只需亚和比较即可。为链表长度
4. 删除只需要将前面非重复元素的指针直接指向后一个非重复的指针或者null（当前为最后一个非重复元素时）

图解

代码

class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null || head.next == null){ 
            return head;    // 当空链表或者只有一个节点时直接返回。
        }
        ListNode ed,poc;    // ed：指向上一个非重复元素， poc：遍历整个链表
        if(head != null && head.val == head.next.val){
            while(head.next != null && head.val == head.next.val){     // 找到第一个非重复元素
                head = head.next;
                if(head.next == null){ //找不到第一个重复元素直接返回空值
                    return null;
                }
                if(head.val != head.next.val){    // 防止a→a→b→b时，a→b时判断失误的情况
                    head = head.next;    
                }
            }
        }
        res = head;
        ed = res;    // 更新ed
        poc = ed.next;    // 接着遍历
        while(poc != null){
            while(poc.next != null && poc.val == poc.next.val){
                if(poc.next.next == null){    // 很重要，当末尾两个元素重复时直接返回
                    ed.next = null;    // 切断链表
                    return res;
                }
                poc = poc.next;
                if(poc.next != null && poc.val != poc.next.val){ // 判断与下一个元素是否重复
                    poc = poc.next;
                }
            }
            ed.next = poc;
            ed = ed.next;    // 更新ed
            poc = poc.next;
        }
        ed.next = null; // 切断链表
        return head;
    }
}

时间复杂度只需要遍历一遍链表就可以

空间复杂度在原链表上修改

方法二：新建链表

解题思路

其实和上面差不多只是上面是在原来的链表上操作，有些复杂的特判(也可能是我太菜了)，如果我们新建一个链表返回那么会简单很多。

首先我们要找到第一个没有重复的元素然后加入新的链表。之后还是遍历原链表，每当我们找到一个没有重复的元素的时候我们将其加入新的链表后面。最后返回新的链表。但是我们要在新链表前加一个头节点方便操作，最后返回即可。

图解

代码

class Solution {
    public ListNode deleteDuplicates (ListNode head) { 
        if(head == null || head.next == null){// 当空链表或者只有一个节点时直接返回。
            return head;
        }
        ListNode res = new ListNode(-1);    // 新建节点
        ListNode poc = res;    // 遍历节点
        int f = -1;    // 当前遍历节点的前一项
        while(head != null){
            if(poc.val != head.val && head.val != head.next.val && head.val != f){    // 不需要特别找出第一个非重复元素
                poc.next = new ListNode(head.val);    // 每找到一个非重复元素加入新的链表后面
                poc = poc.next;
            }
            f = head.val;    //    更新，确保下一次遍历时能对比是否重复
            head = head.next;
            if(head.next == null){    // 当原链表到头
                if(head.val != f){    //    判断最后一个是否需要加入新链表
                    poc.next = new ListNode(head.val);
                }
                break;
            }
        }
        res = res.next;    //    因为第一个是-1
        return res;
    }
}

时间复杂度：只需要遍历一次链表

空间复杂度：需要新建一个链表返回