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

题目链接

描述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.

题目很简单，因为给的是升序链表相同的都挨在一起，所以我们确定链表中一个值是否存在重复只需要判断用一个变量记录下当前值如果链表下一个值等于当前值（）时说明存在重复需要删除直到碰到一个不相等的值后更新即可。

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

解题思路：

我们只要依次遍历链表，然后判断遍历的元素是否存在重复，重复删除，否则留下即可。

所以：

1. 链表第一项跳过（第一项前不仅额能有重复）
2. 第二项开始当时删除

图解

代码

import java.util.*;

class Solution {
    public ListNode deleteDuplicates (ListNode head) { 
        if(head == null){// 当空链表或者只有一个节点时直接返回。
            return head;
        }
        ListNode poc = head;
        ListNode ed = poc;    // ed：指向上一个非重复元素， poc：遍历整个链表
        while(poc != null){    // poc不为空则遍历没结束
            if(ed.val != poc.val){ // 只要和尾部ed不同则为非重复元素
                ed.next = poc;
                ed = ed.next;    // 删除中间重复元素，其实就是把非重复的元素接到前面
            }
            poc = poc.next;    // 遍历
        }
        ed.next = null;    // // 切断链表
        return head;
    }
}

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

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

方法二：新建链表

解题思路

其实和上面差不多只是上面是在原来的链表上操作，但是我们新建一个链表返回。

我们将第一个新节点加入我们新建的链表，之后遍历原来的链表，遍历的过程每次与新的链表尾节点比较，不同时加入新链表，因为新链表的节点都在原链表出现过，相同时一定是重复元素所以跳过即可。

图解

代码

import java.util.*;

class Solution {
    public ListNode deleteDuplicates (ListNode head) { 
        if(head == null){    // 当空链表或者只有一个节点时直接返回。
            return head;
        }
        ListNode res = new ListNode(head.val);    // 新建节点
        ListNode poc = res;    // 遍历节点
        while(head != null){
            if(head.val != poc.val){    // 遍历时找到一个非重复的节点则加入新链表后面
                poc.next = new ListNode(head.val);
                poc = poc.next;
            }
            head = head.next;    // 遍历原链表
        }
        return res;
    }
}

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

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